# A Topology-Aware Localized Update Strategy for Graph-Based ANN Index

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2025.

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

- [The Hybrid Multimodal Graph Index (HMGI): A Comprehensive Framework for Integrated Relational and Vector Search](https://mlsanity.com/paper/2510.10123/) (2025)
- [FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2603.21710/) (2026)
- [SafeQL: Search-based Refinement for Safe and Efficient LLM-based Text-to-SQL](https://mlsanity.com/paper/2608.09260/) (2026)
- [Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2609.23036/) (2026)

## Abstract (arXiv)

The graph-based index has been widely adopted to meet the demand for approximate nearest neighbor search (ANNS) for high-dimensional vectors. However, in dynamic scenarios involving frequent vector insertions and deletions, existing systems improve update throughput by adopting a batch update method. However, a large batch size leads to significant degradation in search accuracy. This work aims to improve the performance of graph-based ANNS systems in small-batch update scenarios, while maintaining high search efficiency and accuracy. We identify two key issues in existing batch update systems for small-batch updates. First, the system needs to scan the entire index file to identify and update the affected vertices, resulting in excessive unnecessary I/O. Second, updating the affected vertices introduces many new neighbors, frequently triggering neighbor pruning. To address these issues, we propose a topology-aware localized update strategy for graph-based ANN index. We introduce a lightweight index topology to identify affected vertices efficiently and employ a localized update strategy that modifies only the affected vertices in the index file. To mitigate frequent heavy neighbor pruning, we propose a similar neighbor replacement strategy, which connects the affected vertices to only a small number (typically one) of the most similar outgoing neighbors of the deleted vertex during repair. Based on extensive experiments on real-world datasets, our update strategy achieves 2.47X-6.45X higher update throughput than the state-of-the-art system FreshDiskANN while maintaining high search efficiency and accuracy.