PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Mengzhao Wang, Xiaoliang Xu, Qiang Yue, Yuxiang Wang

arXiv:2101.12631v2cs.IRcs.DB

TL;DR

Graph-based ANNS lacks a comprehensive, uniform comparison of algorithms’ relative performance, strengths, and pitfalls. This paper evaluates 13 representative algorithms across diverse datasets and finds scenario-dependent recommendations, while its optimized method surpasses state-of-the-art efficiency–accuracy tradeoffs.

  • Problem

    Graph-based ANNS seeks efficient nearest-neighbor retrieval by relaxing accuracy guarantees, but comparative evidence across algorithms’ performance, strengths, and pitfalls remains limited.

  • Method

    The paper develops a taxonomy and unified evaluation framework covering 13 graph-based ANNS algorithms, their components, and performance across eight real-world and 12 synthetic datasets.

  • Results

    The optimized algorithm surpasses state-of-the-art algorithms in efficiency–accuracy tradeoff while maintaining high construction efficiency and low memory overhead.

  • Takeaways & Limitations

    Algorithm choice should follow application scenarios, with recommendations differing by construction cost, graph quality, storage, dataset difficulty, and memory constraints.

  • Takeaways & Limitations

    The study evaluates core algorithms primarily in main memory and leaves hardware, distributed, machine-learning, and structured-attribute settings for future work.

Abstract

from arXiv · show

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.

1 INTRODUCTION

NNS is fundamental across application domains, but dataset growth and dimensionality make accurate search inefficient and costly, motivating ANNS. Graph-based ANNS has emerged as an effective option, yet existing surveys lack comprehensive taxonomy, comparison, and component-level evaluation.

  • ANNS addresses the efficiency–accuracy tradeoff by substantially improving search efficiency while mildly relaxing accuracy constraints.
  • Graph-based ANNS has emerged as a highly effective option among hashing-, tree-, quantization-, and graph-based approaches.
  • Existing surveys cover limited algorithms, datasets, or metrics and largely overlook intra-algorithm components, motivating a broader comparative analysis.
  • Higher graph quality does not necessarily produce better search performance: HNSW and DPG show similar search performance on GIST1M despite graph qualities of 63.3% and 99.2%, respectively.DPG spends substantial time improving graph quality during index construction, according to the supplied passage.
  • The study contributes a fair, comprehensive evaluation using consistent implementations and setups, covering eight real-world and 12 synthetic datasets with diverse characteristics.The evaluation includes algorithms and components, abundant index-construction and search metrics, and scalability across multimedia data including video, voice, image, and text.

2 PRELIMINARIES

This section defines nearest-neighbor search (NNS), approximate nearest-neighbor search (ANNS), and graph-based ANNS, establishing the notation, similarity measure, and scope of the study.

  • Modeling and similarity: Vectors represent dataset points in d-dimensional space, and similarity is commonly computed with Euclidean distance, where smaller values indicate greater similarity.The Euclidean distance is the l2 norm; larger distance values indicate greater dissimilarity.
  • Definitions: NNS returns the k nearest neighbors by evaluating the distance between a query and every dataset point.The formal definition uses a finite dataset in Euclidean space and the Euclidean distance δ(x,q).
  • Definitions: ANNS builds an index to evaluate a small subset of the dataset, trading exactness for efficiency while aiming to maximize Recall@k.On SIFT1M, the evaluated subset may contain only a few thousand points out of millions.
  • Definitions: Graph-based ANNS represents dataset points as vertices and neighbor relationships as edges, then searches from seed points using routing and termination conditions.The graph serves as the ANNS index and updates approximate nearest neighbors during search.
  • Study scope: The survey restricts its comparison to graph-indexed ANNS algorithms because graph-based methods have become mainstream and outperform other index structures in search performance.The stated scope covers graph-based index structures for ANNS.

3 OVERVIEW OF GRAPH-BASED ANNS

This section organizes graph-based ANNS through four foundational base graphs and reviews 13 representative algorithms derived from different optimizations. It explains why the base graphs require adaptation for scalable, high-dimensional search and groups methods by their graph foundations.

  • Base graphs: Four base graphs—Delaunay Graph, Relative Neighborhood Graph, K-Nearest Neighbor Graph, and Minimum Spanning Tree—form the foundation for analyzing graph-based ANNS algorithms.The survey formally describes these graphs and uses a toy example to illustrate their differences.
  • MST-based ANNS: HCNNG uses hierarchical clustering and MST connectivity to construct a graph, exploiting MST’s low degree and global connectivity while risking search detours from its lack of shortcuts.HCNNG follows a divide-and-conquer framework and uses global KD-trees to obtain seeds.
  • Motivation: Directly applying base graphs to ANNS is impractical because construction is difficult to scale, especially for frequently updated and high-dimensional datasets.Their construction complexity and limited high-dimensional search efficiency motivate optimized graph-based algorithms.
  • DG- and RNG-based ANNS: DG- and RNG-based methods optimize navigability and neighbor diversity, but HNSW’s multilayer structure increases memory use and its hierarchy advantage fades above intrinsic dimension 32.The reviewed family includes NSW, HNSW, FANNG, and NGT.
  • KNNG-based ANNS: KNNG-based methods reduce prohibitive exhaustive construction through partitioning, approximate neighbor discovery, or edge pruning, including SPTAG, KGraph, EFANNA, IEH, DPG, NSG, NSSG, and Vamana.These approaches variously target construction cost, neighbor distribution, search performance, and scalability to very large datasets.

4 COMPONENTS’ ANALYSIS

The paper analyzes graph-based ANNS through a unified pipeline with index construction and search as its two coarse-grained components. It further decomposes these into seven fine-grained components, C1–C5 for construction and C6–C7 for search.

  • Index construction: Index construction organizes the dataset into a graph through Divide-and-conquer, Refinement, or Increment strategies across initialization, candidate acquisition, neighbor selection, seed preprocessing, and connectivity.Initialization differs by strategy, while neighbor selection balances distance and spatial distribution factors.
  • Index construction: Neighbor initialization offers high efficiency but low initial graph quality when neighbors are randomly selected, whereas hash-based ANNS, neighborhood propagation, or linear scans can improve initialization.KGraph and Vamana randomly select neighbors; FANNG and IEH initialize neighbors through linear scans.
  • 4 COMPONENTS’ ANALYSIS: The unified pipeline comprises index construction and search, which are subdivided into five and two fine-grained components, respectively.Figure 4 defines C1–C5 for index construction and C6–C7 for search.
  • Search: Search consists of seed acquisition and routing, where routing propagates from seed vertices toward the query and best-first search iteratively expands the closest candidate.State-of-the-art algorithms commonly use seed preprocessing, while best-first search maintains bounded candidate and result sets.

5 EXPERIMENTAL EVALUATION

The evaluation compares 13 graph-based ANNS algorithms across eight real-world and 12 synthetic datasets, measuring search efficiency, accuracy, memory overhead, construction, and graph-related indicators. It finds substantial variation across algorithms and datasets, with distinct trade-offs tied to algorithm category, graph structure, candidate sets, query paths, and implementation components.

  • Construction efficiency and index size: KNNG-based methods such as KGraph and EFANNA have the smallest construction times, while RNG-based methods such as NSG generally produce smaller indexes by cutting redundant edges.Construction time also varies by dataset, and RNG-based methods’ smaller indexes are associated with lower average out-degree.
  • Accuracy and efficiency: Search performance differs substantially across algorithms and datasets; higher speedup generally coincides with higher QPS, indicating that distance-evaluation counts strongly influence efficiency.The study evaluates efficiency with QPS and speedup, accuracy with recall, and also examines candidate-set size and average query-path length.
  • Memory overhead: RNG-based algorithms generally have the smallest memory overhead, whereas additional index structures, larger average out-degree, and larger candidate sets increase memory use.The overall index size is reported as a key determinant of memory overhead during search.
  • Component analysis: Component experiments show that initialization, entry-point acquisition, and other graph-search components materially affect search performance, with hash-based entry acquisition yielding the best performance among the compared entry methods.C4_IEH uses a hash table, while tree-based methods incur different costs depending on whether they require distance calculations.
  • Machine-learning optimizations: The study also evaluates three machine-learning optimizations on NSG and HNSW to improve the speedup-versus-recall trade-off, reporting representative ML1 results in the main text.ML2 and ML3 are described as sharing similar features, with additional results placed in the appendix.

6 DISCUSSION

The discussion presents scenario-specific algorithm recommendations and practical design guidelines, while concluding that the optimized algorithm achieves a superior efficiency–accuracy tradeoff with high construction efficiency and low memory overhead.

  • Recommendations: NSG and NSSG are recommended for S1 because they have the smallest construction time and index size, while KGraph, EFANNA, and DPG suit S2 through high graph quality and lower construction time.
  • Guidelines: The optimized algorithm surpasses state-of-the-art methods in efficiency–accuracy tradeoff while maintaining high construction efficiency and low memory overhead.Figure 11 reports the optimized algorithm’s speedup versus Recall@10.
  • Recommendations: NGT is advantageous for S6 because cache limitations require a smaller candidate set, whereas NSG and NSSG best fit S7 due to low out-degree and memory overhead.
  • Guidelines: The discussion identifies high construction efficiency, routing efficiency, and search accuracy, together with low memory overhead, as practical requirements for graph-based ANNS algorithms.
  • Tendencies: Graph-based ANNS algorithms have evolved from approximating classic base graphs toward optimization-focused methods, with qualitative improvements particularly in search performance.

7 CONCLUSIONS · APPENDIX

The paper surveys and evaluates 13 graph-based ANNS algorithms through a taxonomy and unified framework, while identifying future extensions beyond core main-memory algorithms.

  • 7 CONCLUSIONS: The study organizes 13 representative graph-based ANNS algorithms using a new taxonomy and analyzes them through seven components.The component-level analysis supports a structured comparison of algorithmic approaches.
  • 7 CONCLUSIONS: The authors comprehensively evaluate algorithm performance on eight real-world datasets and 12 synthetic datasets.The evaluation spans both real-world and synthetic data conditions.
  • 7 CONCLUSIONS: The unified framework fairly evaluates each algorithm’s important components.This enables in-depth analysis beyond whole-algorithm performance.
  • 7 CONCLUSIONS: The findings validate many previous empirical conclusions while producing novel discoveries.The study combines confirmation of earlier observations with additional findings.
  • 7 CONCLUSIONS: The current study investigates only core algorithms based on main memory because of various constraints.This limitation defines the scope of the reported analysis.
  • 7 CONCLUSIONS: Future work will examine SSD and GPU hardware, machine-learning optimizations, distributed implementations, and structured attribute constraints for ANNS.These directions extend the study toward hardware, optimization, deployment, and constraint-aware settings.

Appendix A. Proof for the equivalence of the neighbor selection strategies of HNSW and NSG

The appendix proves that HNSW’s heuristic neighbor selection and NSG’s MRNG edge selection use equivalent acceptance conditions. It establishes each strategy’s condition implies the other.

  • HNSW strategy: HNSW selects the closest unvisited candidate m when every selected neighbor n satisfies δ(m,n) > δ(m,p).Candidates are obtained by performing approximate nearest-neighbor search for the inserted point on the partial graph.
  • NSG strategy: NSG selects the closest unvisited candidate m when lune(p,m)∩C is empty or contains no selected neighbor.This is the MRNG edge selection condition applied to candidate set C.
  • Equivalence proof: The proof shows HNSW’s condition implies NSG’s condition by ruling out selected neighbors inside the relevant lune and considering whether remaining candidates intersect it.The argument uses N(p) ⊂ C and separates empty and nonempty intersections with C \ N(p).
  • Equivalence proof: Conversely, the proof shows NSG’s condition implies HNSW’s condition by separately analyzing empty and nonempty lune–candidate intersections.In both cases, the ordering of the closest unvisited candidate establishes δ(m,n) > δ(m,p) for every selected neighbor.
  • Equivalence proof: HNSW and NSG have equivalent neighbor selection strategies.The proof derives NSG’s condition from HNSW’s condition and then derives HNSW’s condition from NSG’s condition.

Appendix B. Proof for the path adjustment of NGT is an approximation to the neighbor selection of RNG

The appendix proves that NGT’s path adjustment approximates RNG neighbor selection by comparing their visitation order and retention criteria across alternative-path cases. The approximation holds for paths of length 2, longer paths, and absent alternative paths.

  • Proof: For a length-2 path p→x→n, NGT deletes n when max{δ(p,x),δ(x,n)} < δ(p,n) and otherwise retains it.The deletion case is consistent with RNG; retention covers the cases where the RNG criterion is met or n is likely selected through x.
  • Proof: When no alternative path exists, NGT also retains n under the stated path-adjustment rule.The path-adjustment definition reserves n when no alternative path exists or its length differs from 2.
  • Proof: NGT visits p’s neighbors in ascending distance order, matching RNG’s selection order for candidate neighbors.The proof therefore focuses on showing that the two methods’ judgment criteria are approximately consistent.
  • Proof: For alternative paths longer than 2 edges, retaining n is consistent with RNG because n and p are likely farther apart and most competing neighbors are farther from n.The argument states that δ(n,p) < δ(n,u) is likely to hold for most other neighbors u of p.
  • Proof: NGT’s path adjustment is an approximation to RNG neighbor selection across the analyzed alternative-path cases.The proof concludes that the path-adjustment operation approximates RNG’s neighbor-selection rule.

Appendix C. Proof for the neighbor selection of DPG is an approximation to that of RNG

The appendix shows that DPG’s neighbor selection approximates NSG’s, which represents RNG’s selection through the equivalence of HNSW and NSG strategies. The proof establishes that NSG-selected neighbors have pairwise angles of at least 60°, a condition DPG can reproduce by maximizing inter-neighbor angles.

  • NSG angle property: NSG’s neighbor-selection strategy guarantees that every pair of selected neighbors around p forms an angle of at least 60°.If a pair had an angle below 60°, triangle-angle reasoning and the NSG exclusion rule would produce a contradiction.
  • DPG selection strategy: DPG selects κ neighbors by maximizing the sum of pairwise angles, and choosing a minimum angle threshold of 60° ensures the NSG selection condition.For the illustrated candidate set, NSG selects {x,z,v}, while DPG selects three neighbors to maximize inter-neighbor angles.
  • Approximation result: DPG’s neighbor selection is an approximation to NSG’s and therefore to RNG’s.The argument uses the approximate representation of RNG by HNSW and the equivalence between HNSW and NSG neighbor selection.

Appendix D. Complexity analysis … Appendix I. Maximum and minimum out-degrees of the graph indexes of the compared algorithms

The appendices document the evaluation methodology, algorithm characteristics and parameters, synthetic-dataset statistics, search procedure, complexity behavior, and graph-index degree limits. Together, they clarify how the compared algorithms were analyzed and how implementation and memory considerations affect evaluation.

  • Appendix D. Complexity analysis: Vamana has the lowest construction complexity among algorithms approximating RNG, while its search complexity is about O(|S|^0.75).The study also reports lower search complexity for DPG, HCNNG, and Vamana than for several alternatives under the evaluated conditions.
  • Appendix E. Characteristics of compared algorithms: The appendices classify algorithms by construction, candidate acquisition, preprocessing, seed acquisition, search strategy, and distance or distribution considerations.The notation distinguishes Best First Search, Guided Search, and Range Search, while Boolean entries indicate whether corresponding processes are ensured.
  • Appendix F. Algorithms description of best first search: Algorithm 1 describes the execution process of best first search over a graph, query, candidate-set size, and seed set to produce a result set.The supplied description identifies the process as BFS but does not provide further execution steps.
  • Appendix H. Parameters of the compared algorithms: Parameter settings are algorithm-specific: KGraph tunes five sensitive parameters, NGT uses range search with epsilon = 1.1, and HNSW controls layer degrees and construction candidates.The appendices also describe EFANNA’s neighbor initialization and update settings and NSSG’s L, R, and Angle parameters.
  • Appendix G. Characteristics of the synthetic datasets: The synthetic datasets are characterized by dimension, cardinality, cluster count, and within-cluster distribution standard deviation.These statistics are summarized for nine synthetic datasets in Table 10.
  • Appendix I. Maximum and minimum out-degrees of the graph indexes of the compared algorithms: Table 11 reports maximum and minimum out-degrees for every compared graph index on the real-world dataset.The appendix notes that maximum-degree alignment can improve search efficiency through continuous memory access, but excessive maximum degrees can exceed memory limits for NSW, DPG, and k-DG.

Appendix J. Scalability of the graph-based ANNS algorithms

The appendix evaluates scalability across dimensionality, cardinality, and dataset characteristics using construction time and query throughput. Construction and search efficiency generally decline as datasets become more challenging, but algorithm categories differ in how well they scale.

  • Dimensionality: As dimensionality increases, construction time rises for most algorithms, while NSW and NGT show the opposite trend and QPS decreases for all algorithms.At very high dimensionality, KNNG- and MST-based methods surpass some RNG-based methods in QPS, despite RNG-based methods leading at lower dimensionality.
  • Dataset characteristics: RNG-based algorithms show the best search scalability across datasets with different characteristics, whereas NN-Descent-based algorithms are most efficient for index construction.The appendix reports that construction and search efficiency decline to varying degrees as dataset characteristics become more demanding.

Appendix K. Components settings for the benchmark algorithm used for components evaluation · Appendix M. Index construction performance of components · Appendix O. Trade-off for efficiency vs accuracy

The appendices specify component-evaluation settings, examine index-construction costs and scalability, and evaluate efficiency–accuracy trade-offs for graph-based ANNS algorithms. They show that graph quality, construction time, and search performance require separate consideration.

  • Appendix K. Components settings for the benchmark algorithm used for components evaluation: The benchmark fixes all non-target components to Table 13 settings during component evaluations.This isolates the effect of the component under study.
  • Appendix M. Index construction performance of components: Index construction time is evaluated for the benchmark algorithm under different iteration counts and component configurations.Tables 14 and 15 provide the corresponding construction-time evaluations.
  • Appendix K. Components settings for the benchmark algorithm used for components evaluation: Different NN-Descent iteration counts are tested because the highest graph quality does not necessarily yield the best search performance.The benchmark selects an iteration value for component evaluation, with the same performance trend observed on two real-world datasets.
  • Appendix M. Index construction performance of components: The appendices report construction, search, and scalability evaluations for k-DR and summarize its component characteristics, parameters, and important attributes.These evaluations use Tables 9–12 and 16–18 and Figures 20–21.
  • Appendix M. Index construction performance of components: NGT constructs indexes faster than k-DR, mainly because NGT initializes an exact KNNG whereas k-DR starts from an approximate graph.The comparison is reported in Table 16.
  • Appendix M. Index construction performance of components: k-DR generally has better scalability than NGT, although their scalability gap gradually narrows.Both methods share path adjustment, but k-DR uses stricter constraints while NGT relaxes them.
  • Appendix O. Trade-off for efficiency vs accuracy: Efficiency–accuracy trade-offs are evaluated using QPS versus Recall@10 and Speedup versus Recall@10 across eight real-world datasets.The analysis emphasizes the high-precision area because ANNS requires a good trade-off between efficiency and accuracy.

Appendix P. Performance evaluation of the optimized algorithm · Appendix Q. Multiple trials for randomized parts of the algorithms

The optimized algorithm (OA) achieves the best overall performance in comparisons with state-of-the-art methods, while randomized algorithms produce results that closely match averages across repeated trials.

  • Appendix P. Performance evaluation of the optimized algorithm: OA achieves the best overall performance against state-of-the-art algorithms in index construction and search evaluations on two real-world datasets.The evaluation uses a common environment and datasets with different difficulty levels.
  • Appendix P. Performance evaluation of the optimized algorithm: The evaluation compares OA and state-of-the-art algorithms using graph quality, average out-degree, connected components, candidate set size, query path length, memory overhead, construction time, and index size.These measures are reported across Tables 19–23, including Table 21 and Table 22’s graph and search-related metrics.
  • Appendix P. Performance evaluation of the optimized algorithm: OA’s index construction efficiency ranks second only to DPG, while outperforming DPG in other evaluated aspects.OA avoids pursuing high graph quality at an expensive construction-time cost.
  • Appendix P. Performance evaluation of the optimized algorithm: OA obtains a smaller index size because it adds no auxiliary structure to the graph index and has a smaller average out-degree.Its neighbor acquisition also avoids distance calculation, and OA preserves accessibility from entries to any o.
  • Appendix Q. Multiple trials for randomized parts of the algorithms: For randomized algorithms, repeated experiments under identical conditions are averaged, and a single trial value is found to be very close to that average.This conclusion is based on the reported results in Table 23, Figure 17, and Figure 18.
  • Appendix Q. Multiple trials for randomized parts of the algorithms: For Vamana, initializing good neighbors yields optimal index construction efficiency, whereas initializing bad neighbors produces the worst efficiency.Good neighbors help Vamana acquire candidate neighbors more efficiently during construction.
  • Appendix Q. Multiple trials for randomized parts of the algorithms: Vamana achieves its best search performance when starting from the best search seeds, while starting from the worst seeds produces the worst search performance.With more than 200 queries, the probability that all randomly obtained seeds are uniformly best or worst is almost zero.
  • Appendix Q. Multiple trials for randomized parts of the algorithms: Because the ratio of best and worst seed outcomes is stable within a query batch, repeated random seeds produce similar search performance.The sufficient query volume makes repeated trials representative of the average behavior.

Appendix R. Evaluation and analysis of machine learn (ML) based methods

This appendix evaluates ML-based graph ANNS methods, which augment existing graph algorithms with learned routing, adaptive termination, or dimensionality reduction. It compares their indexing cost, memory use, and speedup–recall trade-offs under method-specific evaluation constraints.

  • Overview: ML-based methods augment graph ANNS with learned routing, adaptive early termination, or lower-dimensional data mappings.ML1 learns vertex representations, ML2 predicts query-specific stopping points with gradient-boosted trees, and ML3 maps data to lower dimensions.
  • Evaluation: The evaluation compares ML methods on index processing time, memory consumption, and speedup versus recall.These comparisons are summarized in the index-cost table and the speedup–Recall@10 figure for ML-based methods.
  • Evaluation: ML1 requires more than 125G of preprocessing memory on SIFT1M, so experiments use GPU acceleration and the smaller SIFT100K and GIST100K datasets.Because of ML1’s limitation, each query recalls one nearest neighbor and uses Recall@1.
  • Evaluation: The appendix also situates ML-based methods within broader graph-based ANNS comparisons using QPS–Recall@10 and speedup–Recall@10 plots across eight real-world datasets.The plots select optimal indices in the high-precision region, where the top-right is better.
Loading 2101.12631v2…