The compressed cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a k-nearest neighbors algorithm in finite metric spaces. Compressed cover tree is a simplified version of explicit representation of cover tree that was motivated by past issues in proofs of time complexity results of cover tree. The compressed cover tree was specifically designed to achieve claimed time complexities of cover tree Alina Beygelzimer, Sham Kakade, and John Langford. Cover Trees for Nearest Neighbor. In Proc. International Conference on Machine Learning (ICML), 2006. in a mathematically rigorous way.
Problem statement
In the modern formulation, the k-nearest neighbor problem is to find all nearest neighbors in a given reference set R for all points from another given query set Q. Both sets belong to a common ambient space X with a distance metric d satisfying all metric axioms.
Definitions Compressed cover tree
Let (R,d) be a finite metric space. A compressed cover tree has the vertex set R with a root and a level function satisfying the conditions below:
Root condition: the level of the root node r satisfies Covering condition: For every node , we select a unique parent p and a level l(q) such that and this parent node pp has a single link to its child node q.
Separation condition: For , the cover set has
Expansion constants
In a metric space, let be the closed ball with a center p and a radius . The notation denotes the number (if finite) of points in the closed ball.
The expansion constant is the smallest such that for any point and .
the new minimized expansion constant is a discrete analog of the doubling dimension Navigating nets , where A is a locally finite set which covers R.
Note that for any finite metric space (R,d).
Aspect ratio
For any finite set R with a metric d, the diameter is . The aspect ratio is , where is the shortest distance between points of R.
Complexity 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 compressed cover tree it can be bounded: using expansion constant: . using minimized expansion constant / doubling dimension .
K-nearest neighborhood search
Let Q and R be finite subsets of a metric space (X,d). Once all points of R are inserted into a compressed cover tree it can be used for find-queries of the query point set Q. The following time complexities have been proven for finding the k-nearest neighbor of a query point in the reference set R: using expansion constant: . using minimized expansion constant / doubling dimension , where is a number of points inside a closed ball around q having a radius 5 times the distance of q to its k-nearest neighbor.
Space
The compressed cover tree constructed on finite metric space R requires O(|R|) space, during the construction and during the execution of the Find algorithm.
Compared to other similar data structures
Using doubling dimension as hidden factor
Tables below show time complexity estimates which use minimized expansion constant or dimensionality constant related to doubling dimension. Note that denotes the aspect ratio.
Results for building data structures
Name of datastructure, sourceClaimed time complexityClaimed space complexityProof of resultNavigating netsTheorem 2.5Compressed cover treeTheorem 3.6
Results for exact k-nearest neighbors of one query point in reference set R assuming that all data structures are already built. Below we denote the distance between a query point q and the reference set R as and distance from a query point q to its k-nearest neighbor in set R as :
Name of datastructure, sourceClaimed time complexityClaimed space complexityProof of resultNavigating netsProof outline in Theorem 2.3Compressed cover treeCorollary 3.7
Using expansion constant as hidden factor
Tables below show time complexity estimates which use or KR-type constant 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. as a hidden factor. Note that the dimensionality factor is equivalent to
Results for building data structures
Name of datastructure, sourceClaimed time complexityClaimed space complexityProof of resultNavigating netsNot availableCover treeCounterexample 4.2 shows that the past proof is incorrect.Compressed cover treeCorollary 3.10
Results for exact k-nearest neighbors of one query point assuming that all data structures are already built.
Name of datastructure, sourceClaimed time complexityClaimed space complexityProof of resultNavigating netsNot availableCover tree for k = 1.Counterexample 5.2 shows that the past proof is incorrect.Compressed cover treeTheorem 4.9
See also Cover tree Nearest neighbor search k-d tree
References