Pith. sign in

REVIEW 8 cited by

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2101.12631 v2 pith:3YONDHWL submitted 2021-01-29 cs.IR cs.DB

Mengzhao Wang , Xiaoliang Xu , Qiang Yue , Yuxiang Wang This is my paper
classification cs.IRcs.DB
keywords algorithmsannsgraph-basednearestapproachesapproximatecomprehensivedatasets
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 8 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Towards Efficient and Scalable Distributed Vector Search with RDMA

    cs.DC 2025-07 conditional novelty 7.0 of 10

    CoTra runs a shared approximate-nearest-neighbor graph across 16 RDMA-connected machines and reaches 9.8-13.4x single-machine query throughput at 0.95 recall@10.

  2. VecFlow: A High-Performance Vector Data Management System for Filtered-Search on GPUs

    cs.DB 2025-06 conditional novelty 7.0 of 10

    A label-centric GPU index that routes common labels through graph search and rare labels through brute-force scans achieves up to 135x higher filtered-search throughput than previous CPU approaches.

  3. Toward Understanding Bugs in Vector Database Management Systems

    cs.SE 2025-06 conditional novelty 6.0 of 10

    A manual study of 1,463 confirmed bugs in 15 vector database systems yields a taxonomy of 5 symptom categories, 31 root causes, and 12 fix strategies.

  4. DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search

    cs.DB 2025-05 reject novelty 6.0 of 10

    DARTH learns to predict a query's current recall during HNSW/IVF search and stops early at a user-specified target, achieving speedups up to 14.6x on HNSW and 41.8x on IVF, yet 13-15% of queries miss the target.

  5. HENN: A Hierarchical Epsilon Net Navigation Graph for Approximate Nearest Neighbor Search

    cs.DS 2025-05 reject novelty 6.0 of 10

    HENN constructs hierarchical nearest-neighbor graphs with epsilon-net layers, claiming polylogarithmic query time and showing speedups over HNSW on skewed data.

  6. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]

    cs.DB 2025-09 conditional novelty 5.0 of 10

    A systematic benchmark of filtered nearest-neighbor search algorithms shows no single winner: filter-then-search methods excel at containment and equality filters, while hybrid methods dominate overlap filters.

  7. Developing Visual Augmented Q&A System using Scalable Vision Embedding Retrieval & Late Interaction Re-ranker

    cs.IR 2025-07 conditional novelty 4.0 of 10

    A two-stage OpenSearch retriever plus ColPali late-interaction re-ranker matches full late-interaction recall@1 on ViDoRe while using 14 to 53 pages instead of hundreds to thousands per query.

  8. MobileRAG: A Fast, Memory-Efficient, and Energy-Efficient Method for On-Device RAG

    cs.DB 2025-07 conditional novelty 4.0 of 10

    A fully on-device RAG pipeline using a partitioned, partially disk-loaded graph index and selective sentence-window reduction claims 1.72-8.89x faster vector search and up to 40.2% lower power than baselines, with com...

Pith tools