Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree

Posted in Science on August 08, 2008


Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree

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 O(n) space datastructure 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

Author: John Langford, Toyota Technological Institute

Watch Video

Tags: Science, Lectures, Computer Science, VideoLectures.Net