Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN

• URL: http://arxiv.org/abs/2512.09331v1
• Date: Wed, 10 Dec 2025 05:38:59 GMT
• Title: Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN
• Abstract summary: We present BatANN, a distributed disk-based approximate nearest neighbor (ANN) system.<n>Our core innovation is that when accessing a neighborhood which is stored on another machine, we send the full state of the query to the other machine to continue executing there for improved locality.<n>On 100M- and 1B-point datasets at 0.95 recall using 10 servers, BatANN achieves 6.21-6.49x and 2.5-5.10x the throughput of the scatter-gather baseline, respectively.
• Score: 0.7119054550299375
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Vector search underpins modern information-retrieval systems, including retrieval-augmented generation (RAG) pipelines and search engines over unstructured text and images. As datasets scale to billions of vectors, disk-based vector search has emerged as a practical solution. However, looking to the future, we need to anticipate datasets too large for any single server. We present BatANN, a distributed disk-based approximate nearest neighbor (ANN) system that retains the logarithmic search efficiency of a single global graph while achieving near-linear throughput scaling in the number of servers. Our core innovation is that when accessing a neighborhood which is stored on another machine, we send the full state of the query to the other machine to continue executing there for improved locality. On 100M- and 1B-point datasets at 0.95 recall using 10 servers, BatANN achieves 6.21-6.49x and 2.5-5.10x the throughput of the scatter-gather baseline, respectively, while maintaining mean latency below 6 ms. Moreover, we get these results on standard TCP. To our knowledge, BatANN is the first open-source distributed disk-based vector search system to operate over a single global graph.

Related papers

• DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers [9.854925314375024]
  We present DISTRIBUTEDANN, a distributed vector search service that makes it possible to search over a single 50 billion vector graph index spread across over a thousand machines.<n>This is 6x more efficient than existing partitioning and routing strategies that route the vector query to a subset of partitions in a scale out vector search system.
  arXiv  Detail & Related papers  (2025-09-07T13:13:02Z)
• Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search [18.419278931226756]
  SOGAIC is a graph-based ANNS index construction system tailored for ultra-large-scale vector databases.<n>The proposed method has been successfully deployed in a real-world industrial search engine, managing over 10 billion daily updated vectors.
  arXiv  Detail & Related papers  (2025-02-28T04:03:23Z)
• On Storage Neural Network Augmented Approximate Nearest Neighbor Search [1.3654846342364308]
  It is necessary to search for the most similar vectors to a given query vector from the data stored in storage devices, not from that in memory.<n>In this paper, we propose a method to predict the correct clusters by means of a neural network.<n>Compared to state-of-the-art SPANN and an exhaustive method using k-means clustering and linear search, the proposed method achieves 90% recall on SIFT1M with 80% and 58% less data fetched from storage, respectively.
  arXiv  Detail & Related papers  (2025-01-23T06:56:18Z)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  A deep graph clustering method (Dink-Net) is proposed with the idea of dilation and shrink. By discriminating nodes, whether being corrupted by augmentations, representations are learned in a self-supervised manner. The clustering distribution is optimized by minimizing the proposed cluster dilation loss and cluster shrink loss. Compared to the runner-up, Dink-Net 9.62% achieves NMI improvement on the ogbn-papers100M dataset with 111 million nodes and 1.6 billion edges.
  arXiv  Detail & Related papers  (2023-05-28T15:33:24Z)
• Communication-Efficient Graph Neural Networks with Probabilistic Neighborhood Expansion Analysis and Caching [59.8522166385372]
  Training and inference with graph neural networks (GNNs) on massive graphs has been actively studied since the inception of GNNs. This paper is concerned with minibatch training and inference with GNNs that employ node-wise sampling in distributed settings. We present SALIENT++, which extends the prior state-of-the-art SALIENT system to work with partitioned feature data.
  arXiv  Detail & Related papers  (2023-05-04T21:04:01Z)
• TGL: A General Framework for Temporal GNN Training on Billion-Scale Graphs [17.264420882897017]
  We propose TGL, a unified framework for large-scale offline Temporal Graph Neural Network training. TGL comprises five main components, a temporal sampler, a mailbox, a node memory module, a memory updater, and a message passing engine. We introduce two large-scale real-world datasets with 0.2 and 1.3 billion temporal edges.
  arXiv  Detail & Related papers  (2022-03-28T16:41:18Z)
• DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks [58.48833325238537]
  Full-batch training on Graph Neural Networks (GNN) to learn the structure of large graphs is a critical problem that needs to scale to hundreds of compute nodes to be feasible. In this paper, we presentGNN that optimize the well-known Deep Graph Library (DGL) for full-batch training on CPU clusters. Our results on four common GNN benchmark datasets show up to 3.7x speed-up using a single CPU socket and up to 97x speed-up using 128 CPU sockets.
  arXiv  Detail & Related papers  (2021-04-14T08:46:35Z)
• IRLI: Iterative Re-partitioning for Learning to Index [104.72641345738425]
  Methods have to trade between obtaining high accuracy while maintaining load balance and scalability in distributed settings. We propose a novel approach called IRLI, which iteratively partitions the items by learning the relevant buckets directly from the query-item relevance data. We mathematically show that IRLI retrieves the correct item with high probability under very natural assumptions and provides superior load balancing.
  arXiv  Detail & Related papers  (2021-03-17T23:13:25Z)
• Distributed Tera-Scale Similarity Search with MPI: Provably Efficient Similarity Search over billions without a Single Distance Computation [40.75034970144169]
  SLASH is a distributed system for approximate similarity search over terabyte scale datasets. We show how SLASH can index this 2.3 terabyte data over 20 nodes in under an hour, with query times in a fraction of milliseconds.
  arXiv  Detail & Related papers  (2020-08-05T18:15:36Z)
• Superiority of Simplicity: A Lightweight Model for Network Device Workload Prediction [58.98112070128482]
  We propose a lightweight solution for series prediction based on historic observations. It consists of a heterogeneous ensemble method composed of two models - a neural network and a mean predictor. It achieves an overall $R2$ score of 0.10 on the available FedCSIS 2020 challenge dataset.
  arXiv  Detail & Related papers  (2020-07-07T15:44:16Z)
• DDPNAS: Efficient Neural Architecture Search via Dynamic Distribution Pruning [135.27931587381596]
  We propose an efficient and unified NAS framework termed DDPNAS via dynamic distribution pruning. In particular, we first sample architectures from a joint categorical distribution. Then the search space is dynamically pruned and its distribution is updated every few epochs. With the proposed efficient network generation method, we directly obtain the optimal neural architectures on given constraints.
  arXiv  Detail & Related papers  (2019-05-28T06:35:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.