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  ( c  6  n  log  n ) time. Furthermore, nearest neighbor queries require time only logarithmic in  n , in particular  O  ( c  12  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.
['Alina Beygelzimer', 'Sham M. Kakade', 'John Langford']
Cover trees for nearest neighbor