ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms
Top Cited Papers
Open Access
- 20 February 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 270-285
Abstract
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 non-determinism 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.Keywords
All Related Versions
Funding Information
- National Science Foundation (DGE2140739, DGE1745016, CCF-2103483, CCF-2238358, CCF-2227669, CCF-2119352, CCF-1919223, CNS-2317194)
This publication has 29 references indexed in Scilit:
- Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search2016
- Polysemous Codes2016
- Parallelism in Randomized Incremental Algorithms2016
- Numba2015
- A Top-Down Parallel Semisort2015
- Joint Inverted Indexing2013
- Streaming similarity search over one billion tweets using parallel locality-sensitive hashingProceedings of the VLDB Endowment, 2013
- Engineering Efficient and Effective Non-metric Space Library2013
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Thread Scheduling for Multiprogrammed MultiprocessorsTheory of Computing Systems, 2001