Back to Talks

Seminar 1 : Towards efficient nearest neighbor search for manifold data
Speaker : Purushottam Kar
Date : 05:00 pm, Saturday, August 7th, 2010
Venue : CS102

Abstract: Nearest neighbor (NN) search is a ubiquitous operation in learning and allied areas and is used as a subroutine in many tasks such as classification and clustering. As a result, efficient routines for NN search are indispensable for speedy execution of these tasks.

Unfortunately, the NN problem suffers from the curse of dimensionality which typically results in complexity of NN algorithms to be exponential in the ambient dimensionality. In many learning tasks it is observed that data has low ambient dimensionality albeit in a non-linear subspace. The theory of manifolds has been successfully used to understand such datasets.

In this talk we shall outline an approach to NN algorithms that adapt themselves to the ambient manifold dimensionality. More specifically we shall look at the Random Projection Tree data structure (Dasgupta-Freund-STOC-08) and present an approach to NN search using this data structure.

References :
  1. Sanjoy Dasgupta and Yoav Freund, "Random Projection Trees and Low Dimensional Manifolds", STOC, 2008.
  2. Aman Dhesi and Purushottam Kar, "Random Projection Trees Revisited", NIPS, 2010. Cached copy available here.
Back to Talks