# Incremental IVF Index Maintenance for Streaming Vector Search

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 66 references that are in the map.
- First posted on arXiv 1 Nov 2024.

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

- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [A Comprehensive Survey of Deep Learning for Image Captioning](https://mlsanity.com/paper/1810.04020/) (2018)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Deep Image Retrieval: Learning global representations for image search](https://mlsanity.com/paper/1604.01325/) (2016)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [Revisiting the Inverted Indices for Billion-Scale Approximate Nearest Neighbors](https://mlsanity.com/paper/1802.02422/) (2018)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [Related Pins at Pinterest: The Evolution of a Real-World Recommender System](https://mlsanity.com/paper/1702.07969/) (2017)
- [Saga: A Platform for Continuous Construction and Serving of Knowledge At Scale](https://mlsanity.com/paper/2204.07309/) (2022)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment](https://mlsanity.com/paper/2401.02116/) (2024)
- [Constructing Tree-based Index for Efficient and Effective Dense Retrieval](https://mlsanity.com/paper/2304.11943/) (2023)
- [ELIAS: End-to-End Learning to Index and Search in Large Output Spaces](https://mlsanity.com/paper/2210.08410/) (2022)
- [Online Product Quantization](https://mlsanity.com/paper/1711.10775/) (2017)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [Locally-Adaptive Quantization for Streaming Vector Search](https://mlsanity.com/paper/2402.02044/) (2024)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [DiskANN++: Efficient Page-based Search over Isomorphic Mapped Graph Index using Query-sensitivity Entry Vertex](https://mlsanity.com/paper/2310.00402/) (2023)
- [Co-design Hardware and Algorithm for Vector Search](https://mlsanity.com/paper/2306.11182/) (2023)
- [PAM: Parallel Augmented Maps](https://mlsanity.com/paper/1612.05665/) (2016)
- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)

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

- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Pancake: Hierarchical Memory System for Multi-Agent LLM Serving](https://mlsanity.com/paper/2602.21477/) (2026)
- [Cracking Vector Search Indexes](https://mlsanity.com/paper/2503.01823/) (2025)
- [A Super Fast K-means for Indexing Vector Embeddings](https://mlsanity.com/paper/2603.20009/) (2026)
- [How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?](https://mlsanity.com/paper/2512.06200/) (2025)
- [IVF-TQ: Calibration-Free Streaming Vector Search via a Codebook-Free Residual Layer](https://mlsanity.com/paper/2605.17415/) (2026)
- [Submitted and Diagnostic Analysis of Full-Text Temporal Retrieval for LongEval-Sci](https://mlsanity.com/paper/2607.04088/) (2026)

## Abstract (arXiv)

The prevalence of vector similarity search in modern machine learning applications and the continuously changing nature of data processed by these applications necessitate efficient and effective index maintenance techniques for vector search indexes. Designed primarily for static workloads, existing vector search indexes degrade in search quality and performance as the underlying data is updated unless costly index reconstruction is performed. To address this, we introduce Ada-IVF, an incremental indexing methodology for Inverted File (IVF) indexes. Ada-IVF consists of 1) an adaptive maintenance policy that decides which index partitions are problematic for performance and should be repartitioned and 2) a local re-clustering mechanism that determines how to repartition them. Compared with state-of-the-art dynamic IVF index maintenance strategies, Ada-IVF achieves an average of 2x and up to 5x higher update throughput across a range of benchmark workloads.