Related Research Articles
In computing, a cache-oblivious algorithm is an algorithm designed to take advantage of a processor cache without having the size of the cache as an explicit parameter. An optimal cache-oblivious algorithm is a cache-oblivious algorithm that uses the cache optimally. Thus, a cache-oblivious algorithm is designed to perform well, without modification, on multiple machines with different cache sizes, or for a memory hierarchy with different levels of cache having different sizes. Cache-oblivious algorithms are contrasted with explicit loop tiling, which explicitly breaks a problem into blocks that are optimally sized for a given cache.
In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory such as hard drives or tape drives, or when memory is on a computer network. External memory algorithms are analyzed in the external memory model.
In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest node that has both v and w as descendants, where we define each node to be a descendant of itself.
In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but still allows for efficient query operations. The concept was originally introduced by Jacobson to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a compressed data structure, insofar as the size of the stored or encoded data similarly depends upon the specific content of the data itself.
In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.
In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP).
Michael John Fischer is an American computer scientist who works in the fields of distributed computing, parallel computing, cryptography, algorithms and data structures, and computational complexity.
In computer science, a doubly logarithmic tree is a tree where each internal node of height 1, the tree layer above the leaves, has two children, and each internal node of height has children. Each child of the root contains leaves. The number of children at a node from each leaf to root is 0,2,2,4,16, 256, 65536, ...
In computer science, the order-maintenance problem involves maintaining a totally ordered set supporting the following operations:
In computer science, a fractal tree index is a tree data structure that keeps data sorted and allows searches and sequential access in the same time as a B-tree but with insertions and deletions that are asymptotically faster than a B-tree. Like a B-tree, a fractal tree index is a generalization of a binary search tree in that a node can have more than two children. Furthermore, unlike a B-tree, a fractal tree index has buffers at each node, which allow insertions, deletions and other changes to be stored in intermediate locations. The goal of the buffers is to schedule disk writes so that each write performs a large amount of useful work, thereby avoiding the worst-case performance of B-trees, in which each disk write may change a small amount of data on disk. Like a B-tree, fractal tree indexes are optimized for systems that read and write large blocks of data. The fractal tree index has been commercialized in databases by Tokutek. Originally, it was implemented as a cache-oblivious lookahead array, but the current implementation is an extension of the Bε tree. The Bε is related to the Buffered Repository Tree. The Buffered Repository Tree has degree 2, whereas the Bε tree has degree Bε. The fractal tree index has also been used in a prototype filesystem. An open source implementation of the fractal tree index is available, which demonstrates the implementation details outlined below.
Amit Sahai is an American computer scientist. He is a professor of computer science at UCLA and the director of the Center for Encrypted Functionalities.
Martin Farach-Colton is an American computer scientist, known for his work in streaming algorithms, suffix tree construction, pattern matching in compressed data, cache-oblivious algorithms, and lowest common ancestor data structures. He is a Distinguished Professor of computer science at Rutgers University, and a co-founder of storage technology startup company Tokutek.
In computational geometry, a point p in a finite set of points S is said to be maximal or non-dominated if there is no other point q in S whose coordinates are all greater than or equal to the corresponding coordinates of p. The maxima of a point setS are all the maximal points of S. The problem of finding all maximal points, sometimes called the problem of the maxima or maxima set problem, has been studied as a variant of the convex hull and orthogonal convex hull problems. It is equivalent to finding the Pareto frontier of a collection of points, and was called the floating-currency problem by Herbert Freeman based on an application involving comparing the relative wealth of individuals with different holdings of multiple currencies.
ACM SIGARCH is the Association for Computing Machinery's Special Interest Group on computer architecture, a community of computer professionals and students from academia and industry involved in research and professional practice related to computer architecture and design. The organization sponsors many prestigious international conferences in this area, including the International Symposium on Computer Architecture (ISCA), recognized as the top conference in this area since 1975. Together with IEEE Computer Society's Technical Committee on Computer Architecture (TCCA), it is one of the two main professional organizations for people working in computer architecture.
In computer science, the list-labeling problem involves maintaining a totally ordered set S supporting the following operations:
Richard Vuduc is a tenured professor of computer science at the Georgia Institute of Technology. His research lab, The HPC Garage, studies high-performance computing, scientific computing, parallel algorithms, modeling, and engineering. He is a member of the Association for Computing Machinery (ACM). As of 2022, Vuduc serves as Vice President of the SIAM Activity Group on Supercomputing. He has co-authored over 200 articles in peer-reviewed journals and conferences.
References
- ↑ , Department of Computer Science, Stony Brook University, retrieved 2021-12-23.
- 1 2 "Tokutek Founders to Speak at Big Data Techcon San Francisco", Market Wired, October 14, 2014.
- ↑ "Michael Bender - The Mathematics Genealogy Project". www.mathgenealogy.org.
- ↑ Michael A. Bender at the Mathematics Genealogy Project
- ↑ "FAST 17". www.usenix.org.
- ↑ , ACM, retrieved 2021-12-23.
- ↑ "LATIN". latintcs.org. Retrieved 2021-10-08.
- ↑ "IPDPS 2015 Avance Program". ipdps.org. Retrieved 2021-12-13.
- ↑ "Best Papers". usenix.org. Retrieved 2021-11-24.
