A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search

Summary: Comprehensive survey and experimental comparison of 13 graph-based ANNS algorithms, using a new taxonomy and a fine-grained pipeline. Uniform evaluation on eight real-world and twelve synthetic datasets reveals trends, actionable guidance, and principled directions toward improved, state-of-the-art ANNS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12379
Venue: VLDB
Year: 2021
Pagerank: 0.00017896807
Overall Rank: 476 | 96.70%
DOI: 10.14778/3476249.3476255

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 68 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,341	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011194797
1,559	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.0001040748
1,985	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.4487363e-05
2,179	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.0778698e-05
2,199	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.0284127e-05
2,766	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.2159054e-05
2,778	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.1962724e-05
2,796	Similarity search in the blink of an eye with compressed indices	2023	VLDB	8.178491e-05
3,779	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.1851123e-05
3,787	iRangeGraph: Improvising Range-dedicated Graphs for Range-filtering Nearest Neighbor Search	2024	SIGMOD	7.1790151e-05
3,799	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.1682127e-05
4,247	Navigating Labels and Vectors: A Unified Approach to Filtered Approximate Nearest Neighbor Search	2024	SIGMOD	6.8706347e-05
4,520	SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search	2025	SIGMOD	6.7182526e-05
4,560	RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor Search	2024	VLDB	6.6961568e-05
4,890	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.5242948e-05
5,809	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	6.1420277e-05
6,658	Dumpy: A Compact and Adaptive Index for Large Data Series Collections	2023	SIGMOD	5.870738e-05
6,660	AquaPipe: A Quality-Aware Pipeline for Knowledge Retrieval and Large Language Models	2025	SIGMOD	5.8703922e-05
6,746	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8432496e-05
6,950	Steiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes	2024	VLDB	5.8013545e-05
7,182	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB	5.7376349e-05
7,231	UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search	2025	VLDB	5.721049e-05
7,504	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6637827e-05
7,516	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.6614584e-05
7,617	PDX: A Data Layout for Vector Similarity Search	2025	SIGMOD	5.6399054e-05
7,998	GTS: GPU-based Tree Index for Fast Similarity Search	2024	SIGMOD	5.5669146e-05
8,003	TOD: GPU-accelerated Outlier Detection via Tensor Operations	2023	VLDB	5.5660333e-05
8,181	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.5389119e-05
8,193	Accelerating Graph Indexing for ANNS on Modern CPUs	2025	SIGMOD	5.5370767e-05
8,248	DIGRA: A Dynamic Graph Indexing for Approximate Nearest Neighbor Search with Range Filter	2025	SIGMOD	5.5241293e-05
8,249	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD	5.5241293e-05
8,259	DEG: Efficient Hybrid Vector Search Using the Dynamic Edge Navigation Graph	2025	SIGMOD	5.521179e-05
8,359	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB	5.500939e-05
8,924	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	5.4076395e-05
9,219	DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search	2026	SIGMOD	5.3637135e-05
9,546	Cohesiveness-aware Hierarchical Compressed Index for Community Search on Attributed Graphs	2025	SIGMOD	5.316206e-05
9,879	CoTra: Towards Efficient and Scalable Distributed Vector Search with RDMA	2026	SIGMOD	5.2533454e-05
9,910	RWalks: Random Walks as Attribute Diffusers for Filtered Vector Search	2025	SIGMOD	5.2443653e-05
10,006	Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation	2026	PODS	5.1725247e-05
10,031	PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs	2026	SIGMOD	5.1725247e-05
10,039	VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs	2026	SIGMOD	5.1725247e-05
10,042	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD	5.1725247e-05
10,052	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD	5.1725247e-05
10,054	Beyond Vector Search: Querying With and Without Predicates	2026	SIGMOD	5.1725247e-05
10,071	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	5.1725247e-05
10,095	NeurStore: Efficient In-database Deep Learning Model Management System	2026	SIGMOD	5.1725247e-05
10,111	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
10,129	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
10,146	CANDOR-Bench: Benchmarking In-Memory Continuous ANNS under Dynamic Open-World Streams [Experiments & Analysis]	2026	SIGMOD	5.1725247e-05

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
48	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044673733
114	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00032660283
354	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00020437323
368	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020063233
472	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.0001798859
723	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014720507
957	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013044785
2,091	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.254357e-05
5,103	Permutation Search Methods are Efficient, Yet Faster Search is Possible	2015	VLDB	6.4273601e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,575	Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search	2025	VLDB	5.1725247e-05
8,181	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD	5.5389119e-05
10,166	FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
4,890	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.5242948e-05
957	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013044785
10,052	Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study	2026	SIGMOD	5.1725247e-05
10,073	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD	5.1725247e-05
114	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00032660283
10,165	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.1725247e-05
1,341	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011194797