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.

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:.

• Separation:.

Complexity

Find

Like other metric trees. However, in high-dimensional metric spaces constant is non-trivial, 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 is the expansion constant of the dataset.

Insert

time. However, this is an upper-bound, and some techniques have been implemented that seem to improve the performance in practice.

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

• M-tree

References

1. Notes

   Bibliography

2. Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006.

3. JL's Cover Tree page. John Langford's page links to papers and code.

4. A C++ Cover Tree implementation on GitHub.

5. A cover tree implementation in Java.