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

author: John Langford, Toyota Technological Institute at Chicago
published: Feb. 25, 2007,   recorded: August 2004,   views: 12649

Related Open Educational Resources

Related content

Report a problem or upload files

If 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.
Lecture popularity: You need to login to cast your vote.


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 page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 Curtis Autery, July 14, 2009 at 3:40 p.m.:

I enjoyed this lecture, as it is the closest thing I've found to a lay description of cover trees. However, the video coverage of the slideshow was shaky. Do you have a softcopy available?

Comment2 vickey, January 2, 2010 at 3:01 p.m.:

Can you please provide any link to download this video lecture ?
This lecture is quite important for me and I don't have a fast internet connection, so if possible please provide a link to download the lecture.

Write your own review or comment:

make sure you have javascript enabled or clear this field: