Cover trees

The Cover Tree is a special type of data structure in computer science that is specifically designed to facilitate the speed-up of nearest neighbor searches. The tree can be thought of as a hierarchy of levels with the top level containing the root tuple and the bottom level containing every tuple 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: $C_{i}\subset C_{i-1}$
• Covering: For every tuple $p\in C_{i-1}$, there exists a tuple $q\in C_{i}$ 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 tuples $p,q\in C_{i}$, the distance from $p$ to $q$ is greater than $2^{i}$.