Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
Summary: Near-linear algorithm to build proximity graphs for (1+ε)-ANN in doubling metrics with O((1/ε)^λ·n·logΔ) edges and (1/ε)^λ·polylogΔ query time, beating prior Ω(n^2) constructions. Matching lower bounds Ω((1/ε)^λ·n + n·logΔ) on worst-case (non-geometric) inputs and an Euclidean refinement that removes the logΔ factor to O((1/ε)^λ·n) edges while preserving query/construction guarantees. (summarized by gpt-5-mini on Feb 11 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Shangqi Lu (Hong Kong University of Science and Technology)
- 2. Yufei Tao (Chinese University of Hong Kong)
BibTeX Citation
@inproceedings{lu_pods26,
address = {New York, NY, USA},
series = {{PODS} '26},
title = {{Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation}},
url = {https://dl.acm.org/doi/10.1145/3767716},
doi = {10.1145/3767716},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Lu, Shangqi and Tao, Yufei},
year = {2026}
}Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next