Fast Exact High Dimensional Nearest Neighbors
in Arbitrary Dimensions with Cover Trees

John Langford

Abstract

  Given only a metric between points, how quickly can the nearest neighbor of a point be found? In the worst case, this time is O(n). When these points happen to obey a dimensionality constraint, more speed is possible.
The "cover tree" is an O(n) space data structure which allows us to answer queries in O(log(n)) time given a fixed intrinsic dimensionality. It is also a very practical algorithm yielding speedups between a factor of 1 and 1000 on all datasets tested.
This speedup has direct implications for several learning algorithms, simulations, and some systems.


Back to the Main Page

Pradeep Ravikumar
Last modified: Thu Apr 7 19:21:57 EDT 2005