Material Detail

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

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

This video was recorded at Solomon seminar. 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

Quality

  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material

Browse...

Disciplines with similar materials as Fast, Exact Nearest Neighbor in Arbitrary Dimensions with a Cover Tree

Comments

Log in to participate in the discussions or sign up if you are not already a MERLOT member.