A Topology-Aware Localized Update Strategy for Graph-Based ANN Index
Proceedings of the VLDB Endowment · 01.11.2025 · 19 (3) · 495-508
DOI: 10.14778/3778092.3778108 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 18.03.2026. Verfasst von Song Yu und 9 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 79 Literaturangaben.
Abstract (Originalsprache)
Graph-based indices are widely used for approximate nearest neighbor search (ANNS). Under dynamic workloads, existing ANNS systems amortize update overhead with large batches, but large batches degrade index quality. We identify two key limitations in existing systems when handling small-batch updates. First, they still scan the entire index to repair the affected graph topology and rebuild the index, causing heavy I/O. Second, their naive repair introduces many edges, repeatedly triggering costly neighbor pruning with expensive distance computations. To address these issues, we propose a topology-aware localized update strategy that exploits the locality of small-batch updates to reduce unnecessary I/O and computation. Specifically, we introduce a lightweight graph topology that quickly identifies affected nodes without full index scans, and a localized update mechanism that restricts modifications to the pages containing these nodes. Moreover, we design a similarity-aware localized connection method that links each affected node to a small set of highly similar neighbors, avoiding redundant edges and costly pruning. Extensive experiments show that our update strategy achieves 2.39–5.96× higher update throughput than the state-of-the-art graph-based streaming ANNS system FreshDiskANN while maintaining high search efficiency and accuracy.
Zitieren
APA
Yu, S., Lin, S., Gong, S., Xie, Y., Liu, R., Zhou, Y., Sun, J., Zhang, Y., Li, G., & Yu, G. (2025). A Topology-Aware Localized Update Strategy for Graph-Based ANN Index. Proceedings of the VLDB Endowment, 19(3), 495-508. https://doi.org/10.14778/3778092.3778108
Vancouver
Yu S, Lin S, Gong S, Xie Y, Liu R, Zhou Y, et al. A Topology-Aware Localized Update Strategy for Graph-Based ANN Index. Proceedings of the VLDB Endowment. 2025;19(3):495-508. doi:10.14778/3778092.3778108
BibTeX
@article{Yu2025,
author = {Yu, Song and Lin, Shengyuan and Gong, Shufeng and Xie, Yongqing and Liu, Ruicheng and Zhou, Yijie and Sun, Ji and Zhang, Yanfeng and Li, Guoliang and Yu, Ge},
title = {A Topology-Aware Localized Update Strategy for Graph-Based ANN Index},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {19},
number = {3},
pages = {495--508},
doi = {10.14778/3778092.3778108}
}
EUVIMED