A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph
This work addresses a foundational problem in machine learning for researchers and practitioners by bridging empirical practices with theoretical analysis, though it is incremental in extending existing theory to approximate graphs.
The paper tackles the practice-to-theory gap in graph-based nearest neighbor search by providing theoretical guarantees for greedy search on approximate near neighbor graphs for low-dimensional dense vectors, using novel computational geometry tools to quantify trade-offs in approximation.
Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. These empirical successes urge the need for theoretical results that guarantee the search quality and efficiency of these algorithms. However, there exists a practice-to-theory gap in the graph-based NN-Search algorithms. Current theoretical literature focuses on greedy search on exact near neighbor graph while practitioners use approximate near neighbor graph (ANN-Graph) to reduce the preprocessing time. This work bridges this gap by presenting the theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors. To build this bridge, we leverage several novel tools from computational geometry. Our results provide quantification of the trade-offs associated with the approximation while building a near neighbor graph. We hope our results will open the door for more provable efficient graph-based NN-Search algorithms.