Mixing
Cover tree
The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up 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 low-dimensional 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: Ci⊆Ci−1{displaystyle C_{i}subseteq C_{i-1}}
Covering: For every point p∈Ci−1{displaystyle pin C_{i-1}}, there exists a point q∈Ci{displaystyle qin C_{i}}
such that the distance from p{displaystyle p}
to q{displaystyle q}
is less than or equal to 2i{displaystyle 2^{i}}
and exactly one such q{displaystyle q}
Separation: For all points p,q∈Ci{displaystyle p,qin C_{i}}, the distance from p{displaystyle p}
Contents
1 Complexity
1.1 Find
1.2 Insert
1.3 Space
2 See also
3 References
Complexity
Find
Like other metric trees the cover tree allows for nearest neighbor searches in O(η∗logn){displaystyle O(eta *log {n})}
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(c6logn){displaystyle O(c^{6}log {n})}
Space
The cover tree uses implicit representation to keep track of repeated points. Thus, it only requires O(n) space.
See also
- Nearest neighbor search
- kd-tree
References
- Notes
^ Kenneth Clarkson. Nearest-neighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006.
^ http://hunch.net/~jl/projects/cover_tree/cover_tree.html
- Bibliography
- 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.
Comments
Post a Comment