# ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms arXiv: https://arxiv.org/abs/2305.04359 ยท HTML: https://mlsanity.com/paper/2305.04359/ ## Key facts - Cited by 24 papers in the map (data through 14 Oct 2026). - Builds on 14 of its 74 references that are in the map. - First posted on arXiv 7 May 2023. ## Builds on (most cited first, 14 of 14) - [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016) - [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018) - [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015) - [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017) - [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021) - [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022) - [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018) - [Polysemous codes](https://mlsanity.com/paper/1609.01882/) (2016) - [Efficient Large-scale Approximate Nearest Neighbor Search on the GPU](https://mlsanity.com/paper/1702.05911/) (2017) - [Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable](https://mlsanity.com/paper/1805.05208/) (2018) - [Parallel Batch-Dynamic kd-Trees](https://mlsanity.com/paper/2112.06188/) (2021) - [Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism](https://mlsanity.com/paper/2201.13007/) (2022) - [Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient](https://mlsanity.com/paper/2205.13077/) (2022) - [Parallel Longest Increasing Subsequence and van Emde Boas Trees](https://mlsanity.com/paper/2208.09809/) (2022) ## Built on by (most cited first, 24 of 24) - [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023) - [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024) - [LSM-VEC: A Large-Scale Disk-Based System for Dynamic Vector Search](https://mlsanity.com/paper/2505.17152/) (2025) - [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025) - [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025) - [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023) - [B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index](https://mlsanity.com/paper/2511.15557/) (2025) - [Optimizing Domain-Specific Image Retrieval: A Benchmark of FAISS and Annoy with Fine-Tuned Features](https://mlsanity.com/paper/2412.01555/) (2024) - [GPU-Accelerated ANNS: Quantized for Speed, Built for Change](https://mlsanity.com/paper/2601.07048/) (2026) - [UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture](https://mlsanity.com/paper/2410.23805/) (2024) - [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025) - [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025) - [CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2508.02091/) (2025) - [Trading Vector Data in Vector Databases](https://mlsanity.com/paper/2511.07139/) (2025) - [SPI: Query-Depth-Adaptive Indexing for Streaming RAG in Vector Databases](https://mlsanity.com/paper/2511.16681/) (2025) - [Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN](https://mlsanity.com/paper/2512.09331/) (2025) - [Graph-Based Nearest-Neighbor Search without the Spread](https://mlsanity.com/paper/2602.06633/) (2026) - [Welfarist Formulations for Diverse Similarity Search](https://mlsanity.com/paper/2602.08742/) (2026) - [Filtered Approximate Nearest Neighbor Search in Vector Databases: System Design and Performance Analysis](https://mlsanity.com/paper/2602.11443/) (2026) - [Understanding the Performance Plateau in Text-to-Video Retrieval: A Comprehensive Empirical and Linguistic Analysis](https://mlsanity.com/paper/2605.00826/) (2026) - [ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2607.17582/) (2026) - [QASP: Query-Adaptive Robust Vector Search Policy](https://mlsanity.com/paper/2607.29606/) (2026) - [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026) - [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026) ## Abstract (arXiv) Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector space representations (i.e., embeddings) of data. Among various ANNS algorithms, graph-based algorithms are known to achieve the best throughput-recall tradeoffs. Despite the large scale of modern ANNS datasets, existing parallel graph based implementations suffer from significant challenges to scale to large datasets due to heavy use of locks and other sequential bottlenecks, which 1) prevents them from efficiently scaling to a large number of processors, and 2) results in nondeterminism that is undesirable in certain applications. In this paper, we introduce ParlayANN, a library of deterministic and parallel graph-based approximate nearest neighbor search algorithms, along with a set of useful tools for developing such algorithms. In this library, we develop novel parallel implementations for four state-of-the-art graph-based ANNS algorithms that scale to billion-scale datasets. Our algorithms are deterministic and achieve high scalability across a diverse set of challenging datasets. In addition to the new algorithmic ideas, we also conduct a detailed experimental study of our new algorithms as well as two existing non-graph approaches. Our experimental results both validate the effectiveness of our new techniques, and lead to a comprehensive comparison among ANNS algorithms on large scale datasets with a list of interesting findings.