Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree
published: Feb. 25, 2007, recorded: August 2004, views: 2032
Report a problem or upload filesIf you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
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
Link this pageWould you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !