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

The graph-based index has been widely adopted to meet the demand for approximate nearest neighbor search (ANNS) for highdimensional 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 graphbased 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.47×-6.45× higher update throughput than the state-of-the-art system FreshDiskANN while maintaining high search efficiency and accuracy.