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