[talks] S Ravi MSE thesis talk
Melissa M. Lawson
mml at CS.Princeton.EDU
Fri Apr 25 11:11:19 EDT 2014
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
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...
More information about the talks