[talks] S Ravi MSE thesis talk

[Melissa M. Lawson]

Sachin Ravi will present his MSE thesis talk on Thursday May 1 at 2:30 PM 
in Room 301 (note room!). The members of his committee are: Kai Li (advisor) 
and Moses Charikar. Everyone is invited to attend his talk. His abstract 
follows below. 





Nearest Neighbor search is a fundamental problem in computer vision, machine learning, data mining, 
and other fields. In today's Internet age, as the size of images and other non-text data grows 
exponentially, it is crucial to scale solutions to larger datasets. Current research involves the approximate 
nearest neighbor problem where we are willing to sacrice some percentage of accuracy 
so that the approximate algorithm is one or two orders of magnitude faster than a naive linear scan 
of the data. Most recently, advances in performance for the K-Nearest Neighbor (K-NN) search 
problem have been made using a graph-based data structure. 


To this end, we consider adapting a graph-based index for approximate Epsilon-Nearest Neighbor (Epsilon- 
NN) search. Through analysis of various data sets, we show that this problem is very relevant to the 
requirements of current applications. We then introduce a new data structure Epsilon-NN graph for online 
nearest neighbor search and an algorithm for constructing this index on existing data. Through 
experimental evaluation on extracted data sets, we show the high performance of this data structure 
compared to existing methods. 



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20140425/e0c91eeb/attachment.htm>