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.