|
Range Tree
In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the ''k''-d tree. Compared to ''k''-d trees, range trees offer faster query times of (in Big O notation) O(\log^dn+k) but worse storage of O(n\log^ n), where ''n'' is the number of points stored in the tree, ''d'' is the dimension of each point and ''k'' is the number of points reported by a given query. Bernard Chazelle improved this to query time O(\log^ n + k) and space complexity O\left(n\left(\frac\right)^\right). Data structure A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leav ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jon Louis Bentley
Jon Louis Bentley (born February 20, 1953) is an American computer scientist who is credited with the heuristic-based partitioning algorithm ''k''-d tree. Education and career Bentley received a B.S. in mathematical sciences from Stanford University in 1974, and M.S. and PhD in 1976 from the University of North Carolina at Chapel Hill; while a student, he also held internships at the Xerox Palo Alto Research Center and Stanford Linear Accelerator Center. After receiving his Ph.D., he joined the faculty at Carnegie Mellon University as an assistant professor of computer science and mathematics. At CMU, his students included Brian Reid, John Ousterhout, Jeff Eppinger, Joshua Bloch, and James Gosling, and he was one of Charles Leiserson's advisors. Later, Bentley moved to Bell Laboratories, where he co-authored an optimized Quicksort algorithm with Doug McIlroy. He found an optimal solution for the two dimensional case of Klee's measure problem: given a set of ''n'' rectangles, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PAM Library
PAM (Parallel Augmented Maps) is an open-source parallel C++ library implementing the interface for sequence, ordered sets, ordered maps, and augmented maps. The library is available on GitHub. It uses the underlying balanced binary tree structure using join-based algorithms. PAM supports four balancing schemes, including AVL trees, red-black trees, treaps and weight-balanced trees. PAM is a parallel library and is also safe for concurrency. Its parallelism can be supported by cilk, OpenMP or the scheduler in PBBS. Theoretically, all algorithms in PAM are work-efficient and have polylogarithmic depth. PAM uses underlying persistent tree structure such that multi-versioning is allowed. PAM also supports efficient GC. Interface Sequences To define a sequence, users need to specify the key type of the sequence. PAM supports functions on sequences including construction, find an entry with a certain rank, first, last, next, previous, size, empty, filter, map-reduce, concatenatin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
CGAL
The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) are also available. The software is available under dual licensing scheme. When used for other open source software, it is available under open source licenses (LGPL or GPL depending on the component). In other cases commercial license may be purchased, under different options for academic/research and industrial customers. History The CGAL project was founded in 1996, as a consortium of eight research institutions in Europe and Israel: Utrecht University, ETH Zurich, Free University of Berlin, INRIA Sophia Antipolis, Martin-Luther-University Halle-Wittenberg, Max Planck Institute for Informatics Saarbrücken, Johannes Kepler University Linz, and Tel-Aviv University. The original funding for the project came from the ESPRIT project of th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Range Searching
In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points corresponding to the coordinates of several cities, find the subset of cities within a given range of latitudes and longitudes. The range searching problem and the data structures that solve it are a fundamental topic of computational geometry. Applications of the problem arise in areas such as geographical information systems (GIS), computer-aided design (CAD) and databases. Variations There are several variations of the problem, and different data structures may be necessary for different variations. In order to obtain an efficient solution, several aspects of the problem need to be specified: * Object types: Algorithms depend on whether ''S'' consists of points, lines, line segments, boxes, polygons.... The simplest and most studied objects ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Segment Tree
In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure and cannot be modified once built. A similar data structure is the interval tree. A segment tree for a set of ''n'' intervals uses ''O''(''n'' log ''n'') storage and can be built in ''O''(''n'' log ''n'') time. Segment trees support searching for all the intervals that contain a query point in time ''O''(log ''n'' + ''k''), ''k'' being the number of retrieved intervals or segments. Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning. The segment tree can be generalized to higher dimension spaces. Definition Description Let ''S'' be a set of intervals, or segments. Let ''p''1, ''p''2, ..., ''pm'' be the list of distinct interval endpoin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fractional Cascading
In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standard for binary searches, but successive searches in the sequence are faster. The original version of fractional cascading, introduced in two papers by Chazelle and Guibas in 1986 (; ), combined the idea of cascading, originating in range searching data structures of and , with the idea of fractional sampling, which originated in . Later authors introduced more complex forms of fractional cascading that allow the data structure to be maintained as the data changes by a sequence of discrete insertion and deletion events. Example As a simple example of fractional cascading, consider the following problem. We are given as input a collection of ''k'' ordered lists ''Li'' of numbers, such that the total length Σ, ''Li'', of all lists is ''n' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree Traversal
In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well. Types Unlike linked lists, one-dimensional arrays and other linear data structures, which are canonically traversed in linear order, trees may be traversed in multiple ways. They may be traversed in depth-first or breadth-first order. There are three common ways to traverse them in depth-first order: in-order, pre-order and post-order. Beyond these basic traversals, various more complex or hybrid schemes are possible, such as depth-limited searches like iterative deepening depth-first search. The latter, as well as breadth-first search, can also be used to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Range Query (data Structures)
In data structures, a range query consists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array. Definition A range query q_f(A,i,j) on an array A= _1,a_2,..,a_n/math> of ''n'' elements of some set , denoted A ,n/math>, takes two indices 1\leq i\leq j\leq n, a function defined over arrays of elements of and outputs f(A ,j= f(a_i,\ldots,a_j). For example, for f = \sum and A ,n/math> an array of numbers, the range query \sum_ A computes \sum A ,j= (a_i+\ldots + a_j), for any 1 \leq i \leq j \leq n. These queries may be answered in constant time and using O(n) extra space by calculating the sums of the first elements of and storing them into an auxiliary array , such that B /mat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursive Data Type
In computer programming languages, a recursive data type (also known as a recursively-defined, inductively-defined or inductive data type) is a data type for values that may contain other values of the same type. Data of recursive types are usually viewed as directed graphs. An important application of recursion in computer science is in defining dynamic data structures such as Lists and Trees. Recursive data structures can dynamically grow to an arbitrarily large size in response to runtime requirements; in contrast, a static array's size requirements must be set at compile time. Sometimes the term "inductive data type" is used for algebraic data types which are not necessarily recursive. Example An example is the list type, in Haskell: data List a = Nil , Cons a (List a) This indicates that a list of a's is either an empty list or a cons cell containing an 'a' (the "head" of the list) and another list (the "tail"). Another example is a similar singly linked type in Java ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Binary Search Tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree. The time complexity of operations on the binary search tree is directly proportional to the height of the tree. Binary search trees allow binary search for fast lookup, addition, and removal of data items. Since the nodes in a BST are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of binary logarithm. BSTs were devised in the 1960s for the problem of efficient storage of labeled data and are attributed to Conway Berners-Lee and David Wheeler. The performance of a binary search tree is dependent on the order of insertion of the nodes into the tree since arbitrary insertions may lead to degeneracy; several variations of the bi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
