Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates
Proceedings of the VLDB Endowment · 2025-03 · 18 (7) · 2268-2280
DOI: 10.14778/3734839.3734860 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 29.08.2025. Verfasst von Dawei Liu und 5 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 40 Literaturangaben.
Abstract (Originalsprache)
Approximate nearest neighbor (ANN) search on high-dimensional vector data is core functionality in an increasing number of real-world applications. However, most existing methods only focus on accelerating search by means of indexing that assumes that the data is static. The few methods capable of contending with dynamic data often face challenges such as decreased query accuracy following updates and low update efficiency. In this study, we propose Wolverine, the first proposal that, to our knowledge, enables efficient monotonic search path repair, thereby solving the graph-based ANN index update problem. Wolverine repairs disrupted monotonic search paths by adding in-edges to the out-neighbors of a point to be deleted. To improve efficiency, Wolverine+ restricts the search space to be within the 2-hop neighbors of the point to be deleted. In addition, Wolverine++ employs a sophisticated candidate selection policy to find high-quality candidates in the reduced search space, simultaneously improving accuracy and efficiency. An experimental study on 9 real-world datasets demonstrates that Wolverine is capable of accelerating the deletion throughput by up to 11X and achieving more stable recall during updates compared to the state-of-the-art dynamic ANN search method.
Zitieren
APA
Liu, D., Zheng, B., Yue, Z., Ruan, F., Zhou, X., & Jensen, C. S. (2025). Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates. Proceedings of the VLDB Endowment, 18(7), 2268-2280. https://doi.org/10.14778/3734839.3734860
Vancouver
Liu D, Zheng B, Yue Z, Ruan F, Zhou X, Jensen CS. Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates. Proceedings of the VLDB Endowment. 2025;18(7):2268-2280. doi:10.14778/3734839.3734860
BibTeX
@article{Liu2025,
author = {Liu, Dawei and Zheng, Bolong and Yue, Ziyang and Ruan, Fuhao and Zhou, Xiaofang and Jensen, Christian S.},
title = {Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {7},
pages = {2268--2280},
doi = {10.14778/3734839.3734860}
}
EUVIMED