Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search

Summary: Modular, fast routing for distributed ANNS—LSH-based (provable guarantees) and clustering-based (better empirical recall)—decoupling routing from partitioning so any partitioner can be used. Enables balanced graph partitioning at scale, yielding up to 1.72× QPS at 90% 10-recall on billion-scale datasets. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13826
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,566 | 26.50%
DOI: 10.14778/3725688.3725696

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
400	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002427237

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,360	Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring	2005	SIGMOD	8.9605432e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
2,181	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	9.3451821e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	4.1945683e-05
7,544	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	4.7149033e-05
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
770	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016917602
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
562	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020091752