Cover tree

The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speedup of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data structures developed for indexing intrinsically lowdimensional data.^{[1]}
The tree can be thought of as a hierarchy of levels with the top level containing the root point and the bottom level containing every point in the metric space. Each level C is associated with an integer value i that decrements by one as the tree is descended. Each level C in the cover tree has three important properties:
 Nesting:
 Covering: For every point , there exists a point such that the distance from p to q is less than or equal to 2^{i} and exactly one such q is a parent of p.
 Separation: For all points , the distance from p to q is greater than 2^{i}.
Contents
Complexity
Find
Like other metric trees the cover tree allows for nearest neighbor searches in O(η * log n) where η is a constant associated with the dimensionality of the dataset and n is the cardinality. To compare, a basic linear search requires O(n), which is a much worse dependence on n. However, in highdimensional metric spaces the η constant is nontrivial, which means it cannot be ignored in complexity analysis. Unlike other metric trees, the cover tree has a theoretical bound on its constant that is based on the dataset's expansion constant or doubling constant (in the case of approximate NN retrieval). The bound on search time is O(c^{12}log n) where c is the expansion constant of the dataset.
Insert
Although cover trees provide faster searches than the naive approach, this advantage must be weighed with the additional cost of maintaining the data structure. In a naive approach adding a new point to the dataset is trivial because order does not need to be preserved, but in a cover tree it can take O(c^{6}log n) time. However, this is an upperbound, and some techniques have been implemented that seem to improve the performance in practice.^{[2]}
Space
The cover tree uses implicit representation to keep track of repeated points. Thus, it only requires O(n) space.
See also
References
 ^ Kenneth Clarkson. Nearestneighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, NearestNeighbor Methods for Learning and Vision: Theory and Practice, pages 1559. MIT Press, 2006.
 ^ http://hunch.net/~jl/projects/cover_tree/cover_tree.html
 Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.
 JL's Cover Tree page. John Langford's page links to papers and code.
 A C++ Cover Tree implementation on GitHub.
Trees in computer science Binary trees Selfbalancing binary search trees Btrees B+ tree · B*tree · B^{x}tree · UBtree · 23 tree · 234 tree · (a,b)tree · Dancing tree · HtreeTries Binary space partitioning (BSP) trees Nonbinary trees Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree · Van Emde Boas treeSpatial data partitioning trees Other trees Heap · Hash tree · Finger tree · Metric tree · Cover tree · BKtree · Doublychained tree · iDistance · Linkcut tree · Fenwick treeCategories: Trees (structure)
 Algorithm stubs
Wikimedia Foundation. 2010.
Look at other dictionaries:
tree — noun ADJECTIVE ▪ deciduous, evergreen ▪ coniferous ▪ native ▪ exotic, tropical ▪ ornamental … Collocations dictionary
Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… … Wikipedia
Tree house — Tree houses, treehouses, or tree forts, are buildings constructed among the branches, around or next to the trunk of one or more mature trees, and are raised above the ground. Tree houses are built and used for recreation, as temporary retreats,… … Wikipedia
Tree Pangolin — Tree Pangolin[1] Conservation status … Wikipedia
Tree Solitaire — Tree SolitaireTree solitaire is a special form of solitaire in which cards are laid out as follows: Row one One card Row two Two cards Row three Three cards Row four Four cards Row five Five cards Row six Six Cards Row seven Seven cardsAll rows… … Wikipedia
Tree of life — For other uses, see Tree of life (disambiguation). An 1847 depiction of the Norse Yggdrasil as described in the Icelandic Prose Edda by Oluf Olufsen Bagge The concept of a tree of life, a many branched tree illustrating the idea that all life on… … Wikipedia
Tree inventory — A tree inventory is the gathering of accurate information on the health and diversity of the community forest. [http://www.canr.uconn.edu Connecticut cooperative extension forestry] Uses Tree inventories focus on the attributes of individual… … Wikipedia
Tree of Life (JudeoChristian) — See also Tree of life for other cultural interpretations of the term, and : Tree of life (disambiguation) for other meanings of the term. The Tree of Life (Heb. עץ החיים Etz haChayim ), in the Book of Genesis is a tree planted by God in midst of… … Wikipedia
Tree line — The tree line or timberline is the edge of the habitat at which trees are capable of growing. Beyond the tree line, they are unable to grow because of inappropriate environmental conditions (usually cold temperatures, insufficient air pressure,… … Wikipedia
cover — {{Roman}}I.{{/Roman}} noun 1 sth put on/over sth ADJECTIVE ▪ protective ▪ removable, reversible ▪ leather, plastic ▪ dust … Collocations dictionary