PaperlayerView exact revision on arXiv

Source-linked AI summary

ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms

Magdalen Dobson Manohar, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, Yihan Sun

arXiv:2305.04359v2cs.IRcs.LG

TL;DR

Approximate nearest-neighbor search is widely used in modern AI applications, making scalable and efficient parallel solutions increasingly important. ParlayANN develops deterministic parallel implementations of four graph-based algorithms; these achieve the best recall–QPS tradeoffs across the recall spectrum, while PyNNDescent does not scale to billion-point datasets.

  • Problem

    Scalable, efficient parallel ANNS is increasingly important because embeddings and similarity search are central to many modern AI applications.

    Source: §1 · p. 1

  • Method

    ParlayANN combines general parallel graph-building techniques with deterministic implementations of four state-of-the-art graph-based ANNS algorithms.

    Source: §1 · pp. 2–3

  • Results

    Graph-based implementations achieve the best recall–QPS tradeoffs across the recall spectrum; non-graph approaches failed to exceed 95% recall on billion-size datasets, even at very low QPS.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On out-of-distribution queries, graph-based algorithms adapt better than existing non-graph implementations in achieving high recall.

    Source: §5.6 · p. 10, §7 · p. 12

    Despite optimization, PyNNDescent did not scale to billion-point datasets, though it achieved reasonable QPS and recall on inputs with ∼100 million points.

    Source: §4.4 · p. 7

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses parallel graph-based ANNS implementations that struggle to scale and can produce nondeterministic graphs, alongside a lack of benchmarking at billion scale. ParlayANN introduces deterministic parallel implementations and evaluates their scalability and query quality against graph and non-graph approaches.

1 Introduction

  • Existing lock-based parallel graph implementations scale only to tens of threads and produce nondeterministic graphs, problematic for persistence, crash recovery, and replication.The paper also notes that existing benchmarks generally focus on million-scale inputs and sequential performance.Source: §1 · p. 2
  • ParlayANN applies parallel techniques to four state-of-the-art graph-based algorithms, yielding deterministic implementations with better scalability than the existing implementations.The algorithms are DiskANN, HNSW, HCNNG, and PyNNDescent.Source: §1 · p. 2
  • On 1M points, the new implementations scale across all 48 cores, with further performance improvements from hyperthreading.Figure 1 compares speedups against each original implementation's one-thread running time.Source: §1 · p. 2, Figure 1 · p. 3
  • Across billion-scale experiments, graph-based implementations achieve the best recall–QPS tradeoffs, while non-graph approaches fail to exceed 95% recall even at very low QPS.The study covers diverse real-world datasets, including OOD queries.Source: §1 · p. 2
  • The work combines general and algorithm-specific parallelization techniques with a unified library and an experimental study of billion-scale datasets.The study includes two non-graph approaches and an OOD-query dataset.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries define the parallel model and key terms used to describe approximate nearest-neighbor search. They specify determinism, semisort, and the paper’s recall convention.

2 Preliminaries

  • A parallel computation is deterministic when its output is unchanged across runs and unaffected by the runtime scheduler; randomized algorithms treat their random seed as input.Source: §2 · p. 3
  • Parallel semisort groups entries with equal keys consecutively without requiring the entries or keys to be fully sorted.Source: §2 · p. 3
  • k-NNS returns k points whose distances to the query are no greater than those of any points outside the returned set.Source: §2 · p. 3
  • Throughout the paper, “recall” means average 10@10 recall over the query set.Source: §2 · p. 3

3 General Techniques for Graph-Based ANNS Algorithms

Graph-based ANNS builds a directed proximity graph and answers queries with greedy beam search. The section develops parallel techniques for incremental and clustering-based graph construction, targeting deterministic execution without per-point locks.

3 General Techniques for Graph-Based ANNS Algorithms

  • Greedy beam search expands the closest unprocessed candidate by adding its out-neighbors, retaining at most the beam width L and stopping when all beam vertices have been processed.A proximity graph combines nearby connections with longer edges.Source: §3 · p. 3, Figure 2 · p. 4

3.1 Incremental Algorithms

  • Incremental insertion searches the existing graph, prunes candidates to select bounded-degree out-neighbors, and adds reverse edges so the new point can be reached.Existing parallel insertions can use per-point locks, causing performance issues and nondeterminism.Source: §3.1 · p. 4
  • Prefix doubling inserts exponentially growing batches from a fixed prior-index snapshot, enabling deterministic parallel progress without conflicts within each batch.Batch sizes are capped by θ to preserve information in later rounds; the paper sets θ to 0.02n and reports ParlayDiskANN within 1% of sequential-index QPS at the same recall on BIGANN-1M.Source: §3.1 · pp. 4–5
  • Batch insertion builds each new point’s neighborhood independently on an immutable snapshot, then groups reverse edges by existing vertex with parallel semisort to avoid locks.Source: §3.1 · p. 5

3.2 Clustering-Based Algorithms

  • Clustering-based methods build local graphs in recursively split clusters, but parallelizing only across trees limits scaling, while lock-based edge merging and costly local structures add bottlenecks.HCNNG and PyNNDescent use clustering trees.Source: §3.2 · p. 5
  • The general clustering approach parallelizes each tree’s construction and both branches of its divide-and-conquer splits, then uses semisort to group edges before merging them without per-point locks.Parallel partitioning assigns points to branches; exposing more parallelism can create space issues for HCNNG.Source: §3.2 · p. 5

4 ParlayANN Algorithms

ParlayANN adapts four graph-based ANNS algorithms with parallel construction techniques and algorithm-specific changes. It also optimizes search structures and procedures, while PyNNDescent remains limited to roughly 100-million-point inputs.

4.1 DiskANN

  • ParlayDiskANN applies prefix doubling for hundreds of cores and uses triangle-based pruning to remove long edges and reduce graph degree.The pruning rule filters visited points when they are α times closer to a selected neighbor than to the point being pruned.Source: §4.1 · p. 6

4.2 HNSW

  • ParlayHNSW uses batch insertion at each hierarchy layer with parallel prefix doubling and removes locks from its internal data structures.HNSW searches from the top layer downward, using the current result as the next layer’s entry point.Source: §4.2 · p. 6

4.3 HCNNG

  • ParlayHCNNG’s edge-restricted MST reduces temporary memory and improves parallelism with no QPS drop at a given recall; it is up to 12× faster than original HCNNG.Instead of considering all pairwise edges, the MST uses each point’s 10 nearest neighbors.Source: §4.3 · p. 6

4.4 PyNNDescent

  • ParlayPyNN limits degree during edge undirecting and batches two-hop neighborhood work, enabling scale to 100M points but not billions because of temporary-memory demands.Its nearest-neighbor-descent rounds retain the K closest candidates from each point’s two-hop neighborhood and stop when few edges change.Source: §4.4 · pp. 6–7

4.5 Search and Layout Optimizations

  • Across the search implementations, an approximate visited-set hash table improves performance by 28.6%–44.5%; fixed-length edge lists avoid graph-layout indirection.The table is sized to the square of the beam width to fit in first-level cache, making revisits rare; search also uses (1 + ε) pruning with ε at most .25.Source: §4.5 · p. 7

5 Experimental Evaluations

The evaluation compares ParlayANN implementations with existing graph and non-graph algorithms across million-, hundred-million-, and billion-scale settings. It reports strong graph-based recall–QPS trade-offs at billion scale, while also examining scalability and dataset-size effects.

5.1 Experimental Setup

  • The experiments use BIGANN, MSSPACEV, and TEXT2IMAGE datasets, report build time and QPS using all threads unless stated otherwise, and sweep search parameters for recall–QPS curves.The target regime is recall .9 to .999; the setup also compares the original graph implementations and, at larger scales, FAISS and FALCONN.Source: §5.1 · pp. 7–8

5.2 Comparison with ANN Benchmarks

  • The single-thread ParlayANN results on BIGANN-1M roughly match public ANN Benchmarks numbers; FALCONN is excluded from later figures because of poor performance.Figure 5 reports single-thread QPS on BIGANN-1M for comparison with ANN Benchmarks.Source: §5.2 · p. 8, Figure 5 · p. 10

5.3 Parallelism and Scalability

  • ParlayDiskANN improves performance about 1.2×, ParlayHNSW reaches 1.4×, ParlayHCNNG 12×, and ParlayPyNN 28× over their original implementations.The original DiskANN and HNSW implementations encounter locking-related scaling issues; HCNNG and PyNNDescent also have thread-scaling limits.Source: §5.3 · p. 8

5.4 Full Billion-Scale and Hundred-Million Results

  • All graph implementations build billion-scale indexes in around 10 hours; ParlayHNSW builds up to 2.3× faster, while ParlayDiskANN usually leads on query performance.The query comparison is based on the recall–QPS curve.Source: §5.4 · p. 8, Figure 3 · p. 9
  • FAISS usually builds 1.5–3× faster than graph algorithms, but stays below 0.8 recall on BIGANN and MSSPACEV even at very low QPS.Its QPS is orders of magnitude lower than graph algorithms at higher recall, though the gap is smaller at lower recall.Source: §5.4 · pp. 8–9
  • On OOD TEXT2IMAGE, graph algorithms reach recall of at least 0.8, but their QPS is 12.2–19.6× lower than on non-OOD datasets at the same recall.ParlayDiskANN reaches recall 0.9 on this dataset.Source: §5.4 · p. 10

5.5 Dataset Size Scaling

  • When MSSPACEV grows 10×, graph-based build times rise 11–12×; ParlayDiskANN and ParlayHNSW also lose QPS at fixed 0.8 recall as larger graphs require wider searches.For DiskANN and HNSW, larger graphs make beam search slower and less accurate at unchanged parameters.Source: §5.5 · p. 10

5.6 Conclusions from Experiments

  • Graph-based algorithms achieve recall above .9 at 10k–200k QPS on billion-scale datasets; non-graph approaches struggle at high recall, especially on OOD queries.The experiments conclude that graph-based methods reach at least 0.8 recall on OOD data, while IVF approaches struggle to reach 0.2.Source: Figure 3 · p. 9, §5.6 · p. 10

6 Related Work

Related work spans graph, inverted-index, hashing, and tree-based ANNS, while prior billion-scale studies and benchmarks leave gaps in comparable evidence across algorithms and parallel settings.

6 Related Work

  • ANNS approaches include proximity-graph search, IVF posting-list search, and trees, with LSH also used to assign vectors to inverted-index buckets.The paper focuses on graph-index construction, while noting related work on intra-query parallelism and scalable tree methods.Source: §6 · p. 11
  • Tree methods suit low-dimensional metric spaces, but their search faces the curse of dimensionality despite modified high-dimensional variants.Source: §6 · p. 11
  • Billion-scale IVF studies report BIGANN and DEEP results, but omit graph comparisons and focus on single-neighbor rather than k-neighbor recall.Source: §6 · p. 11
  • Secondary-storage systems include DiskANN and SPANN, but reported comparisons are limited and single-query latency reflects constraints on concurrent throughput.SPANN reports billion-scale results on BIGANN, DEEP, and MSSPACEV, comparing only with DiskANN.Source: §6 · p. 11
  • GPU IVF results report low recall and narrow system comparisons, while BLISS reports HNSW numbers over an order of magnitude worse than those found here.Other billion-plus-point systems do not report comparative numbers.Source: §6 · p. 11
  • ANN Benchmarks covers up to nine million-scale datasets, while the Billion Scale ANNS Challenge spans three hardware tracks and six billion-size datasets.Both are valuable resources, but user-sourced implementations can differ and may not isolate algorithmic ideas.Source: §6 · pp. 11–12

7 Conclusion and Future Work

ParlayANN implements four deterministic parallel graph-based algorithms for billion-scale inputs on one machine, avoiding locks and achieving high recall. The conclusion highlights HCNNG’s performance and open questions on OOD queries, quantization, and range search.

7 Conclusion and Future Work

  • ParlayANN implements four deterministic parallel graph-based algorithms for billion-scale inputs on one machine, avoiding locks and outperforming non-graph implementations at high recall, especially on OOD queries.Source: §7 · p. 12
  • HCNNG’s strong performance is surprising, motivating the question of whether incremental graph techniques can combine with HCNNG insights to dominate both.Source: §7 · p. 12
  • IVF and LSH show a clear inability to answer OOD queries, prompting the question of how to adapt them for better OOD performance.Source: §7 · p. 12
  • The paper identifies efficient, deterministic parallelization of quantization—and its effect on ANNS algorithm choice—as an open direction.Source: §7 · p. 12
  • How graph-based and other ANNS algorithms adapt to billion-scale or larger range-search problems remains an open question.Source: §7 · p. 12

A Algorithm Parameters

The appendix describes dataset-specific build settings for four graph algorithms and FAISS, including parameter tradeoffs and configuration choices for different scales.

A Algorithm Parameters

  • DiskANN uses degree bound R, insertion beam width L, and pruning parameter α; settings target recall .94–.97 because no setting is optimal across recall regimes.For TEXT2IMAGE, α must be at most 1.0 to select a denser graph.Source: A Algorithm Parameters · p. 14
  • HNSW uses degree bound m, build beam width efc, and density parameter α, with bottom-layer degree 2m matched to DiskANN’s R.The experiments keep 2m = R and efc = L, adjusting α for similar average bottom-layer degree.Source: A Algorithm Parameters · p. 14
  • HCNNG uses clustering-tree leaf size, MST degree, and tree count; experiments use leaf size 1000, MST degree 3, and 30–50 trees.QPS began to increase above 50 trees.Source: A Algorithm Parameters · p. 14
  • pyNNDescent parameters include degree bound K, pruning α, tree count T, and leaf size L_s, with degree bounds of 40–60 working for most datasets.Source: A Algorithm Parameters · p. 14
  • FAISS settings combine the build transform, IVF type, and query PQ compression; parameters were adjusted toward high recall beyond space-optimized defaults.For 100M slices, Figure 8 compares QPS across centroid counts using 96 threads; Figure 7 lists billion-scale settings.Source: A Algorithm Parameters · pp. 14–15, Figure 7 · p. 15, Figure 8 · p. 15
  • For 100M-scale MSSPACEV and BIGANN, no single FAISS option dominates, so two builds are included.Source: A Algorithm Parameters · p. 15

Related papers

Loading 2305.04359v2…