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