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.