Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree
author:
John Langford,
Toyota Technological Institute at Chicago
Description
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
You might be experiencing some problems with Your Video player.
Lecture rating
| People found this lecture: | ||
| Worth seeing | ||
| because it is: | ||
| Valuable and informative | ||
| Well presented | ||
| Easily understandable | ||
| Acceptably recorded | ||
| You need to login to cast your vote. | ||
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.
Related content
Visitors who watched this lecture also watched...
  49 comments
|
||||
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !
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?
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.
Thanks