Improved fast graph construction for better nearest neighbor search
Fast Sparse $α$-Navigable Graph Construction with Improved Resource Augmentation
Data Structures and Algorithms
Summary
Finding points closest to a given one in large datasets is a key problem in computing. The authors study a special kind of directed graph that helps find approximate nearest neighbors quickly by following paths in the graph. They present a faster method to build such graphs that uses fewer connections while maintaining good search accuracy. Their method also shows that making these improvements faster is likely very hard without new ideas. This work helps improve tools that rely on quick similarity searches.
What this means in practice
- •For data engineers: Construct search graphs for approximate nearest neighbor queries with better balance of speed and memory use.
- •For computer vision teams: Build efficient sparse graphs for fast image similarity search in large visual databases.
Authors
Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Ben Landrum, Christopher Musco, Yarin Shechter, Torsten Suel, Richard Wen
Abstract
Graph-based nearest neighbor search methods, which run greedy search on a directed graph over the data points, have surged in popularity in recent years. A common goal is to construct a search graph with the $α$-navigability property, which ensures that greedy search returns provably good approximate nearest neighbors and converges in few iterations. Increasing $α\geq 1$ improves accuracy and convergence rate, but requires more edges, which increases both space and search time. This tradeoff has motivated the study of algorithms for constructing a sparsest $α$-navigable graph for a given set of points. For any point set and any distance function, we show how to compute an $α$-navigable graph with at most $O(\log n)$ times as many edges as the sparsest $(1+\varepsilon)α$-navigable graph, in $O(n^ω\log(Δ)/\varepsilon)$ time, where $ω< 2.372$ is the matrix multiplication exponent and $Δ$ is the aspect ratio of the input. This improves on Khanna, Padaki, and Waingarten (SODA 2026), who achieve the same runtime but are only competitive with the sparsest $2(1+\varepsilon)α$-navigable graph. Since sparsity often increases rapidly with $α$ (typically $α\leq 1.1$), their bound can be significantly weaker. Previously, the best algorithm competing with the sparsest $(1+\varepsilon)α$-navigable graph required $\widetilde{O}(n^{2.5})$ time. Our techniques also extend to constructing sparse $τ$-monotonic graphs, another popular target in nearest neighbor search. Finally, we give a fine-grained complexity analysis suggesting that improving the $O(n^ω)$ running time is unlikely, or would require a very different approach. It is based on hardness results for problems related to verifying whether a graph is navigable, a topic of independent interest.