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: ${\displaystyle C_{i}\subseteq C_{i-1}}$
• Covering: For every point ${\displaystyle p\in C_{i-1}}$, there exists a point ${\displaystyle q\in C_{i}}$ such that the distance from ${\displaystyle p}$ to ${\displaystyle q}$ is less than or equal to ${\displaystyle 2^{i}}$ and exactly one such ${\displaystyle q}$ is a parent of ${\displaystyle p}$.
• Separation: For all points ${\displaystyle p,q\in C_{i}}$, the distance from ${\displaystyle p}$ to ${\displaystyle q}$ is greater than ${\displaystyle 2^{i}}$.