Local Search Methods for Fast Near Neighbor Search.
Eric S. Téllez, Guillermo Ruíz, Edgar Chávez, Mario Graff · arXiv (Cornell University) · 2017
Near neighbor search is a powerful abstraction for data access; it allows searching for objects similar to a query. Search indexes are data structures designed to accelerate computing-intensive data processing, like those routinely found in clustering and classification tasks. However, for intrinsically high-dimensional data, competitive indexes tend to have either impractical index construction times or memory usage. A recent turn around in the literature has been introduced with the use of the approximate proximity graph (APG): a connected graph with a greedy search algorithm with restarts, needing sublinear time to solve queries. The APG computes an approximation of the result set using a small memory footprint, i.e., proportional to the underlying graph's degree. The degree along with the number of search repeats determine the speed and accuracy of the algorithm. This manuscript introduces three new algorithms based on local-search metaheuristics for the search graph. Two of these algorithms are direct improvements of the original one, yet we reduce the number of free parameters of the algorithm; the third one is an entirely new method that improves both the search speed and the accuracy of the result in most of our benchmarks. We also provide a broad experimental study to characterize our search structures and prove our claims; we also report an extensive performance comparison with the current alternatives.