# SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 53 references that are in the map.
- First posted on arXiv 5 Nov 2021.

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

- [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)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (2016)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [Pyramid: A General Framework for Distributed Similarity Search](https://mlsanity.com/paper/1906.10602/) (2019)
- [Composite Quantization](https://mlsanity.com/paper/1712.00955/) (2017)

## Built on by (most cited first, 30 of 35)

- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [Revisiting a kNN-based Image Classification System with High-capacity Storage](https://mlsanity.com/paper/2204.01186/) (2022)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Uni-Retriever: Towards Learning The Unified Embedding Based Retriever in Bing Sponsored Search](https://mlsanity.com/paper/2202.06212/) (2022)
- [Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings](https://mlsanity.com/paper/2204.00185/) (2022)
- [Human-inspired Perspectives: A Survey on AI Long-term Memory](https://mlsanity.com/paper/2411.00489/) (2024)
- [TeleRAG: Efficient Retrieval-Augmented Generation Inference with Lookahead Retrieval](https://mlsanity.com/paper/2502.20969/) (2025)
- [ESPN: Memory-Efficient Multi-Vector Information Retrieval](https://mlsanity.com/paper/2312.05417/) (2023)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [Co-design Hardware and Algorithm for Vector Search](https://mlsanity.com/paper/2306.11182/) (2023)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [Hierarchical Patch Compression for ColPali: Efficient Multi-Vector Document Retrieval with Dynamic Pruning and Quantization](https://mlsanity.com/paper/2506.21601/) (2025)
- [Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval](https://mlsanity.com/paper/2210.05521/) (2022)
- [Hallmarks of Optimization Trajectories in Neural Networks: Directional Exploration and Redundancy](https://mlsanity.com/paper/2403.07379/) (2024)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Multimodal Data Storage and Retrieval for Embodied AI: A Survey](https://mlsanity.com/paper/2508.13901/) (2025)
- [Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph](https://mlsanity.com/paper/2509.25487/) (2025)
- [QVCache: A Query-Aware Vector Cache](https://mlsanity.com/paper/2602.02057/) (2026)
- [CaGR-RAG: Context-aware Query Grouping for Disk-based Vector Search in RAG Systems](https://mlsanity.com/paper/2505.01164/) (2025)
- [GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions](https://mlsanity.com/paper/2602.16719/) (2026)
- [SIFT: Selective-Index For Fast Compute of RAG Prefill by Exploiting Attention Invariance](https://mlsanity.com/paper/2606.09441/) (2026)
- [MINT: Multi-Vector Search Index Tuning](https://mlsanity.com/paper/2504.20018/) (2025)
- [Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces](https://mlsanity.com/paper/2506.06557/) (2025)
- [Large-Scale Graph Building in Dynamic Environments: Low Latency and High Quality](https://mlsanity.com/paper/2507.10139/) (2025)
- [Individualized non-uniform quantization for vector search](https://mlsanity.com/paper/2509.18471/) (2025)
- [ARCADE: A Real-Time Data System for Hybrid and Continuous Query Processing across Diverse Data Modalities](https://mlsanity.com/paper/2509.19757/) (2025)
- [MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search](https://mlsanity.com/paper/2601.01930/) (2026)
- [EGA: Adapting Frozen Encoders for Vector Search with Bounded Out-of-Distribution Degradation](https://mlsanity.com/paper/2605.05674/) (2026)
- [IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer](https://mlsanity.com/paper/2605.17415/) (2026)

## Abstract (arXiv)

The in-memory algorithms for approximate nearest neighbor search (ANNS) have achieved great success for fast high-recall search, but are extremely expensive when handling very large scale database. Thus, there is an increasing request for the hybrid ANNS solutions with small memory and inexpensive solid-state drive (SSD). In this paper, we present a simple but efficient memory-disk hybrid indexing and search system, named SPANN, that follows the inverted index methodology. It stores the centroid points of the posting lists in the memory and the large posting lists in the disk. We guarantee both disk-access efficiency (low latency) and high recall by effectively reducing the disk-access number and retrieving high-quality posting lists. In the index-building stage, we adopt a hierarchical balanced clustering algorithm to balance the length of posting lists and augment the posting list by adding the points in the closure of the corresponding clusters. In the search stage, we use a query-aware scheme to dynamically prune the access of unnecessary posting lists. Experiment results demonstrate that SPANN is 2× faster than the state-of-the-art ANNS solution DiskANN to reach the same recall quality 90% with same memory cost in three billion-scale datasets. It can reach 90% recall@1 and recall@10 in just around one millisecond with only 32GB memory cost. Code is available at: footnotesizecolorblueurlhttps://github.com/microsoft/SPTAG.