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
| CREATOR | Shangqi Lu, Yufei Tao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 80 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07732