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

By Mengzhao Wang, Xiaoliang Xu, Qiang Yue, Yuxiang Wang. Proceedings of the VLDB Endowment, 2021

376 citations recorded by the source corpus.

Approximate nearest neighbor search (ANNS) constitutes an important operation in a multitude of applications, including recommendation systems, information retrieval, and pattern recognition. In the past decade, graph-based ANNS algorithms have been the leading paradigm in this domain, with dozens of graph-based ANNS algorithms proposed. Such algorithms aim to provide effective, efficient solutions for retrieving the nearest neighbors for a given query. Nevertheless, these efforts focus on developing and optimizing algorithms with different approaches, so there is a real need for a comprehensive survey about the approaches' relative performance, strengths, and pitfalls. Thus here we provide a thorough comparative analysis and experimental evaluation of 13 representative graph-based ANNS algorithms via a new taxonomy and fine-grained pipeline. We compared each algorithm in a uniform test environment on eight real-world datasets and 12 synthetic datasets with varying sizes and characteristics. Our study yields novel discoveries, offerings several useful principles to improve algorithms, thus designing an optimized method that outperforms the state-of-the-art algorithms. This effort also helped us pinpoint algorithms' working portions, along with rule-of-thumb recommendations about promising research directions and suitable algorithms for practitioners in different fields.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f1613881b5f90cd779bf9c8511f3af410ce49846

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

The Faiss Library (2024, positive): “This empirical complexity analysis has been used before for graph-based indices [73].”
What Drives Cross-lingual Ranking? Retrieval Approaches with Multilingual Language Models (2025, unknown): “To support scalability, particularly in dense retrieval, ANN search is employed to reduce inference overhead [33, 34], though its behaviour under cross-lingual conditions is less thoroughly explored [35].”
VIBE: Vector Index Benchmark for Embeddings (2025, unknown): “More recent performance evaluations (Wang et al., 2021; Azizi et al., 2025) consider only graph-based ANN methods and do not provide an open and extensible benchmarking framework.”
MINT: Multi-Vector Search Index Tuning (2025, unknown): “For example, most graph-based indexes need hundreds of seconds to create for one million items [23].”