DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers

• URL: http://arxiv.org/abs/2509.06046v1
• Date: Sun, 07 Sep 2025 13:13:02 GMT
• Title: DISTRIBUTEDANN: Efficient Scaling of a Single DISKANN Graph Across Thousands of Computers
• Abstract summary: 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.
• Score: 9.854925314375024
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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 that offers 26ms median query latency and processes over 100,000 queries per second. 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. DISTRIBUTEDANN is built using two well-understood components: a distributed key-value store and an in-memory ANN index. DISTRIBUTEDANN has replaced conventional scale-out architectures for serving the Bing search engine, and we share our experience from making this transition.

Related papers

• Filtered Vector Search in a Disaggregated Lakehouse: Composing Table-Format Pruning with Per-File ANN [1.0109137908797041]
  We embed an IVF index in each Parquet file's footer.<n>The planner prunes data files by the predicate first, then runs IVF only over the survivors.<n>On an 11.5M x 768 table, warm IVF search is 32x faster than brute force at recall@10 >= 0.90.
  arXiv  Detail & Related papers  (2026-08-05T22:20:01Z)
• Multiple Index Merge for Approximate Nearest Neighbor Search [14.386466486046814]
  This paper focuses on efficient two-index merging and the merge order of multiple indexes for AKNN search.<n>We propose a reverse neighbor sliding merge (RNSM) that exploits structural information to boost merging efficiency.<n> Experiments show that our approach yields up to a 5.48$times$ speedup over existing index merge methods and 9.92$times$ speedup over index reconstruction.
  arXiv  Detail & Related papers  (2026-02-19T05:50:34Z)
• Rethinking ANN-based Retrieval: Multifaceted Learnable Index for Large-scale Recommendation System [46.70111672855811]
  MultiFaceted Learnable Index (MFLI) is a scalable, real-time retrieval paradigm that learns multifaceted item embeddings and indices within a unified framework.<n>MFLI improves recall on engagement tasks by up to 11.8%, cold-content delivery by up to 57.29%, and semantic relevance by 13.5% compared with prior state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-18T01:31:29Z)
• Passing the Baton: High Throughput Distributed Disk-Based Vector Search with BatANN [0.7119054550299375]
  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.
  arXiv  Detail & Related papers  (2025-12-10T05:38:59Z)
• VIBE: Vector Index Benchmark for Embeddings [5.449089394751681]
  We introduce Vector Index Benchmark for Embeddings (VIBE), an open source project for benchmarking ANN algorithms.<n>VIBE contains a pipeline for creating benchmark datasets using dense embedding models characteristic of modern applications.<n>We use VIBE to conduct a comprehensive evaluation of SOTA vector indexes, benchmarking 21 implementations on 12 in-distribution and 6 out-of-distribution datasets.
  arXiv  Detail & Related papers  (2025-05-23T12:28:10Z)
• Cost-Effective, Low Latency Vector Search with Azure Cosmos DB [14.76627855468578]
  We argue that a scalable, high-performance, and cost-efficient vector search system can be built inside a cloud-native operational database like Azure Cosmos DB.<n>This system uses a single vector index per partition stored in existing index trees, and kept in sync with underlying data.<n>It supports 20ms query latency over an index spanning 10 million vectors, has stable recall over updates, and offers approximately 43x and 12x lower query cost compared to Pinecone and Zil Disk serverless enterprise products.
  arXiv  Detail & Related papers  (2025-05-09T08:53:59Z)
• 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)
• AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval [1.099532646524593]
  We propose All-in-Storage ANNS with Product Quantization (AiSAQ), which offloads compressed vectors to the SSD index.<n>Our method achieves $sim$10 MB memory usage in query search with billion-scale datasets without critical latency degradation.
  arXiv  Detail & Related papers  (2024-04-09T04:20:27Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• 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)
• Towards Improving the Consistency, Efficiency, and Flexibility of Differentiable Neural Architecture Search [84.4140192638394]
  Most differentiable neural architecture search methods construct a super-net for search and derive a target-net as its sub-graph for evaluation. In this paper, we introduce EnTranNAS that is composed of Engine-cells and Transit-cells. Our method also spares much memory and computation cost, which speeds up the search process.
  arXiv  Detail & Related papers  (2021-01-27T12:16:47Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• 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)
• DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
  We present a divide-and-conquer (DC) approach to effectively and efficiently search deep neural architectures. We achieve a $75.1%$ top-1 accuracy on the ImageNet dataset, which is higher than that of state-of-the-art methods using the same search space.
  arXiv  Detail & Related papers  (2020-05-29T09:02: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.