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.
Each level C is associated with an integer value i that decrements by one as the tree is descended.
is a constant associated with the dimensionality of the dataset and n is the cardinality.
To compare, a basic linear search requires
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 or doubling constant (in the case of approximate NN retrieval).
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
However, this is an upper-bound, and some techniques have been implemented that seem to improve the performance in practice.
[2] The cover tree uses implicit representation to keep track of repeated points.