Cover trees for nearest neighbor

Alina Beygelzimer, Sham Kakade, John LangfordICML 2006 · OpenReview

Nearest neighbor search (NNS) is a cornerstone algorithm in machine learning, utilized in applications ranging from image recognition to bioinformatics. The premise is simple: given a dataset of points and a query, find the closest point in the set.

However, NNS famously suffers from the "curse of dimensionality." In high-dimensional spaces, traditional spatial data structures like KD-trees degrade, often performing no better than a brute-force linear search. While researchers have proposed various "metric-tree" structures to handle complex, non-Euclidean data, many of these solutions either lack rigorous theoretical guarantees or require prohibitive amounts of memory. For instance, the "navigating net"—a predecessor to the cover tree—only achieves linear space if the dataset's intrinsic dimension is assumed to be constant, an assumption that rarely holds in practice.

To address these shortcomings, this paper introduces the Cover Tree, a specialized data structure designed for fast nearest neighbor searches in any general metric space. By maintaining a hierarchy of "covers" at different scales, cover trees achieve provably fast query times while strictly requiring only linear space ($O(n)$)—a significant improvement over previous structures that explode in size as data dimensionality increases.

The Cover Tree Data Structure

The Cover Tree is a leveled tree where each level acts as a "cover" for the level beneath it. It is defined by three strict invariants:

  1. Nesting: Once a point appears at a certain level, it appears in all lower levels.
  2. Covering: Every point in a lower level must have a "parent" in the level above it within a specific distance (scaled by $2^i$ for level $i$).
  3. Separation: Points at the same level must be sufficiently far apart from each other.

The authors distinguish between an implicit representation (which conceptually has infinite levels) and an explicit representation. The explicit version "collapses" nodes that only have one child. This compression is the key innovation that ensures the tree only uses $O(n)$ space, regardless of the data's dimensionality or expansion constant.

The paper provides a comprehensive suite of algorithms for operating on the cover tree, including a level-by-level Find-Nearest descent that prunes branches incapable of containing the nearest neighbor, dynamic Insert/Remove updates that maintain the tree invariants, and Lazy Construction, a "just-in-time" approach that builds the tree as queries are made.

Theoretical Guarantees

A major contribution of the cover tree is its theoretical robustness. Unlike previous metric data structures where space complexity depended heavily on the "expansion constant" $c$ (a measure of intrinsic dimensionality), cover trees are guaranteed to use $O(n)$ space.

Furthermore, the search speed depends on the intrinsic structure of the data rather than the ambient number of features. If the data sits on a low-dimensional manifold within a high-dimensional space, the cover tree efficiently exploits that geometry.

Theoretical performance bounds of the Cover Tree compared to previous structures.

As shown in the performance bounds, for a dataset with an expansion constant $c$, the cover tree achieves $O(c^{12} \log n)$ query time and $O(c^6 n \log n)$ construction time. By simplifying the directed acyclic graph of the navigating net into a strict tree (where each node has exactly one parent), the authors made the algorithms easier to implement and analyze without sacrificing these theoretical efficiencies.

Empirical Performance

The authors evaluated the cover tree on a diverse range of real-world datasets, including standard ML benchmarks (Iris, Wine, MNIST), high-dimensional data (the KDD 2004 championship dataset), and non-vector data (strings compared using edit distance).

Key Results: * Massive Speedups: On natural machine learning datasets, the cover tree was 1 to 2000 times faster than a brute-force search. * Outperforming Competitors: The cover tree significantly outperformed Clarkson’s $sb(S)$ data structure, particularly in construction time (often 10-30x faster) and memory efficiency. * The 80% Rule: The authors discovered that the "worst-case" expansion constant is a poor predictor of actual performance. Instead, the expansion constant of the 80th percentile of points much more accurately predicts the practical speedup the tree will provide. * Versatility: The structure proved highly effective for non-Euclidean metrics, demonstrating strong speedups on string datasets using edit distance.

Limitations and Future Work

The most notable theoretical limitation is the constant $c$ in the exponent (e.g., $c^{12}$ for queries). While the authors note this is a very loose upper bound and actual empirical performance is vastly better, reducing this theoretical dependence remains an open challenge. Additionally, while the cover tree handles "general" metric spaces, it strictly requires the distance function to satisfy the triangle inequality. Future work could explore how these structures behave with "near-metrics" that slightly violate these rules, a common scenario in modern machine learning applications.

Summary updated

Abstract

We present a tree data structure for fast nearest neighbor operations in general n-point metric spaces (where the data set consists of n points). The data structure requires O(n) space regardless of the metric's structure yet maintains all performance properties of a navigating net (Krauthgamer & Lee, 2004b). If the point set has a bounded expansion constant c, which is a measure of the intrinsic dimensionality, as defined in (Karger & Ruhl, 2002), the cover tree data structure can be constructed in O (c6n log n) time. Furthermore, nearest neighbor queries require time only logarithmic in n, in particular O (c12 log n) time. Our experimental results show speedups over the brute force search varying between one and several orders of magnitude on natural machine learning datasets.
BibTeX
@inproceedings{beygelzimer2006cover,
  author = {Alina Beygelzimer and Sham Kakade and John Langford},
  title = {{Cover trees for nearest neighbor}},
  booktitle = {International Conference on Machine Learning},
  year = {2006},
  url = {https://openreview.net/forum?id=r1-aMiWuZH},
}
Figure