<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Sachin Ravi will present his MSE thesis talk on Thursday May 1 at 2:30 PM <br>in Room 301 (note room!). The members of his committee are: Kai Li (advisor)<br>and Moses Charikar. Everyone is invited to attend his talk. His abstract <br>follows below.<br><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div><font size="2"><br></font></div><div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">Nearest Neighbor search is a fundamental problem in computer vision, machine learning, data mining,</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">and other fields. In today's Internet age, as the size of images and other non-text data grows</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">exponentially, it is crucial to scale solutions to larger datasets. Current research involves the approximate</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">nearest neighbor problem where we are willing to sacrice some percentage of accuracy</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">so that the approximate algorithm is one or two orders of magnitude faster than a naive linear scan</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">of the data. Most recently, advances in performance for the K-Nearest Neighbor (K-NN) search</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">problem have been made using a graph-based data structure.</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2"><br></font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">To this end, we consider adapting a graph-based index for approximate Epsilon-Nearest Neighbor (Epsilon-</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">NN) search. Through analysis of various data sets, we show that this problem is very relevant to the</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">requirements of current applications. We then introduce a new data structure Epsilon-NN graph for online</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">nearest neighbor search and an algorithm for constructing this index on existing data. Through</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">experimental evaluation on extracted data sets, we show the high performance of this data structure</font></div><div style="margin: 0px; font-size: 10px; "><font face="arial,helvetica,sans-serif" size="2">compared to existing methods.</font></div></div><div style="margin: 0px; font-size: 10px; "><br></div><br></div><br></div></body></html>