# B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index

arXiv: https://arxiv.org/abs/2511.15557 · HTML: https://mlsanity.com/paper/2511.15557/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 19 Nov 2025.

## Builds on (most cited first, 15 of 15)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [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)
- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [MTRAG: A Multi-Turn Conversational Benchmark for Evaluating Retrieval-Augmented Generation Systems](https://mlsanity.com/paper/2501.03468/) (2025)
- [A Survey on Locality Sensitive Hashing Algorithms and their Applications](https://mlsanity.com/paper/2102.08942/) (2021)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Long Document Re-ranking with Modular Re-ranker](https://mlsanity.com/paper/2205.04275/) (2022)
- [HyperRAG: Enhancing Quality-Efficiency Tradeoffs in Retrieval-Augmented Generation with Reranker KV-Cache Reuse](https://mlsanity.com/paper/2504.02921/) (2025)
- [Enabling Cognitive Intelligence Queries in Relational Databases using Low-dimensional Word Embeddings](https://mlsanity.com/paper/1603.07185/) (2016)

## Built on by (most cited first, 2 of 2)

- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)
- [Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings](https://mlsanity.com/paper/2608.14648/) (2026)

## Abstract (arXiv)

Storing and processing of embedding vectors by specialized Vector databases (VDBs) has become the linchpin in building modern AI pipelines. Most current VDBs employ variants of a graph-based ap- proximate nearest-neighbor (ANN) index algorithm, HNSW, to an- swer semantic queries over stored vectors. Inspite of its wide-spread use, the HNSW algorithm suffers from several issues: in-memory design and implementation, random memory accesses leading to degradation in cache behavior, limited acceleration scope due to fine-grained pairwise computations, and support of only semantic similarity queries. In this paper, we present a novel disk-based ANN index, B+ANN, to address these issues: it first partitions input data into blocks containing semantically similar items, then builds an B+ tree variant to store blocks both in-memory and on disks, and finally, enables hybrid edge- and block-based in-memory traversals. As demonstrated by our experimantal evaluation, the proposed B+ANN disk-based index improves both quality (Recall value), and execution performance (Queries per second/QPS) over HNSW, by improving spatial and temporal locality for semantic operations, reducing cache misses (19.23% relative gain), and decreasing the memory consumption and disk-based build time by 24x over the DiskANN algorithm. Finally, it enables dissimilarity queries, which are not supported by similarity-oriented ANN indices.