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)

Paper ID: 1996
Venue: PODS
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,007 | 30.39%
DOI: 10.1145/3767716

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Shangqi Lu
2. Yufei Tao

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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.

Rank	Cited Paper	Year	Venue	Pagerank
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
770	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016917602
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05
2,690	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.293714e-05
2,811	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	8.0806307e-05
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
4,731	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	5.966659e-05
5,184	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	5.6406991e-05
5,233	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	5.6131833e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,554	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS	4.1945683e-05
770	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016917602
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	4.1945683e-05
4,724	Nearest-Neighbor Searching Under Uncertainty	2012	PODS	5.9697823e-05
212	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00033913475
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
2,023	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	9.7544991e-05
5,569	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	5.4290942e-05
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05