# Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2018.

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

- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [Residual Quantization with Implicit Neural Codebooks](https://mlsanity.com/paper/2401.14732/) (2024)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Integrating Language Guidance into Vision-based Deep Metric Learning](https://mlsanity.com/paper/2203.08543/) (2022)
- [Planning Ahead in Generative Retrieval: Guiding Autoregressive Generation through Simultaneous Decoding](https://mlsanity.com/paper/2404.14600/) (2024)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [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)
- [OOD-DiskANN: Efficient and Scalable Graph ANNS for Out-of-Distribution Queries](https://mlsanity.com/paper/2211.12850/) (2022)
- [Taxonomy-guided Semantic Indexing for Academic Paper Search](https://mlsanity.com/paper/2410.19218/) (2024)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph](https://mlsanity.com/paper/2303.06210/) (2023)
- [Memoria: Resolving Fateful Forgetting Problem through Human-Inspired Memory Architecture](https://mlsanity.com/paper/2310.03052/) (2023)
- [ESPN: Memory-Efficient Multi-Vector Information Retrieval](https://mlsanity.com/paper/2312.05417/) (2023)
- [Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval](https://mlsanity.com/paper/2201.05409/) (2022)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [Curator: Efficient Indexing for Multi-Tenant Vector Databases](https://mlsanity.com/paper/2401.07119/) (2024)
- [HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]](https://mlsanity.com/paper/2505.01538/) (2025)
- [Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval](https://mlsanity.com/paper/2210.05521/) (2022)
- [B+ANN: A Fast Billion-Scale Disk-based Nearest-Neighbor Index](https://mlsanity.com/paper/2511.15557/) (2025)
- [ARM 4-BIT PQ: SIMD-based Acceleration for Approximate Nearest Neighbor Search on ARM](https://mlsanity.com/paper/2203.02505/) (2022)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)
- [LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table](https://mlsanity.com/paper/2506.04790/) (2025)
- [CNN with large memory layers](https://mlsanity.com/paper/2101.11685/) (2021)
- [SAUCE: Truncated Sparse Document Signature Bit-Vectors for Fast Web-Scale Corpus Expansion](https://mlsanity.com/paper/2108.11948/) (2021)
- [Inverted Semantic-Index for Image Retrieval](https://mlsanity.com/paper/2206.12623/) (2022)
- [Vector search with small radiuses](https://mlsanity.com/paper/2403.10746/) (2024)

## Abstract (arXiv)

This work addresses the problem of billion-scale nearest neighbor search. The state-of-the-art retrieval systems for billion-scale databases are currently based on the inverted multi-index, the recently proposed generalization of the inverted index structure. The multi-index provides a very fine-grained partition of the feature space that allows extracting concise and accurate short-lists of candidates for the search queries. In this paper, we argue that the potential of the simple inverted index was not fully exploited in previous works and advocate its usage both for the highly-entangled deep descriptors and relatively disentangled SIFT descriptors. We introduce a new retrieval system that is based on the inverted index and outperforms the multi-index by a large margin for the same memory consumption and construction complexity. For example, our system achieves the state-of-the-art recall rates several times faster on the dataset of one billion deep descriptors compared to the efficient implementation of the inverted multi-index from the FAISS library.