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

Shangqi Lu, Yufei Tao · 2025

Read Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation by Shangqi Lu, Yufei Tao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07732.txt.

Description

Shangqi Lu and 1 co-author give fresh theory in 2025 for proximity graphs, the data structures behind fast similarity search. Approximate nearest neighbor search finds near matches to a query point in huge datasets. Graph-based methods lead the field in practice. They connect each point to nearby points, and queries walk the graph. Their foundations were incomplete, though.

The authors build a proximity graph with near-linear construction time. That improves on the quadratic bounds of all past constructions. Query time stays controlled by the data's doubling dimension and aspect ratio. Lower bounds then show a matching limit. Worst-case graphs need at least a set number of edges, up to small factors. Their hard examples are non-geometric. That prompts the question of whether Euclidean space allows smaller graphs. Using geometry, they answer yes. They shrink the graph further for that key case.

Catalog record

CREATORShangqi Lu, Yufei Tao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-07732

Browse the full library · About the Tower of Babel