Cover trees for nearest neighbor

TLDR

We present a tree data structure for fast nearest‑neighbor operations in general n‑point metric spaces. The cover tree uses O(n) space, can be built in O(c⁶ n log n) time when the point set has bounded expansion constant c, and supports queries in O(c¹² log n) time. Experimental results show speedups over brute‑force search ranging from one to several orders of magnitude on natural machine‑learning datasets.

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.