Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation

Proximity graph-based methods have emerged as a leading paradigm for approximate nearest neighbor (ANN) search in the system community. This paper presents fresh insights into the theoretical foundation of these methods. We describe an algorithm to build a proximity graph for $(1+ε)$-ANN search that has $O((1/ε)^λ\cdot n \log Δ)$ edges and guarantees $(1/ε)^λ\cdot \text{polylog }Δ$ query time. Here, $n$ and $Δ$ are the size and aspect ratio of the data input, respectively, and $λ= O(1)$ is the doubling dimension of the underlying metric space. Our construction time is near-linear to $n$, improving the $Ω(n^2)$ bounds of all previous constructions. We complement our algorithm with lower bounds revealing an inherent limitation of proximity graphs: the number of edges needs to be at least $Ω((1/ε)^λ\cdot n + n \log Δ)$ in the worst case, up to a subpolynomial factor. The hard inputs used in our lower-bound arguments are non-geometric, thus prompting the question of whether improvement is possible in the Euclidean space (a key subclass of metric spaces). We provide an affirmative answer by using geometry to reduce the graph size to $O((1/ε)^λ\cdot n)$ while preserving nearly the same query and construction time.