EUVIMEDEUVIMED entdecken
Crossref

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

Song Yu, Shengyuan Lin, Shufeng Gong, Yongqing Xie, Ruicheng Liu, Yijie Zhou, Ji Sun, Yanfeng Zhang, Guoliang Li, Ge Yu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →