Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates

Summary: Wolverine: a monotonic search-path repair framework for dynamic graph-based ANN indices that fixes broken monotonic paths by adding in-edges to out-neighbors of deleted nodes to preserve connectivity and recall. Wolverine+ (2‑hop restriction) and Wolverine++ (quality-driven candidate selection) speed deletions up to 11× and maintain steadier recall vs. prior dynamic ANN methods across 9 real datasets. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 14065
Venue: VLDB
Year: 2025
Pagerank: 5.3016261e-05
Overall Rank: 9,236 | 36.64%
DOI: 10.14778/3734839.3734860

Incoming Non-self Citations Over Time

Authors

1. Dawei Liu (Huazhong University of Science and Technology)
2. Bolong Zheng (Huazhong University of Science and Technology)
3. Ziyang Yue (Huazhong University of Science and Technology)
4. Fuhao Ruan (Huazhong University of Science and Technology)
5. Xiaofang Zhou (Hong Kong University of Science and Technology)
6. Christian S. Jensen (Aalborg University)

BibTeX Citation

@article{liu_vldb25,
        title = {{Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-based ANN Index Updates}},
        author = {Liu, Dawei and Zheng, Bolong and Yue, Ziyang and Ruan, Fuhao and Zhou, Xiaofang and Jensen, Christian S.},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {7},
        pages = {2268--2280},
        doi = {10.14778/3734839.3734860},
        url = {https://doi.org/10.14778/3734839.3734860},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,251	GPS: Revisiting the Data Layout for Disk-based High-Dimensional Vector Search	2026	SIGMOD	5.093636e-05
10,299	Through the Lens of Hubness: A Revisit on Graph-Based Approximate Nearest Neighbor Search: [Experiments & Analysis]	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
1,084	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00012256753
1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011508159
1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010407159
3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.5711218e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
2	10,417	WoW: A Window-to-Window Incremental Index for Range-Filtering Approximate Nearest Neighbor Search	2026	SIGMOD
3	6,334	MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Search	2025	SIGMOD
4	93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
5	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
6	9,892	Accelerating Approximate Nearest Neighbor Search in Hierarchical Graphs: Efficient Level Navigation with Shortcuts	2025	VLDB
7	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
8	1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD
9	6,615	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB
10	10,362	Dynamically Detect and Fix Hardness for Efficient Approximate Nearest Neighbor Search	2026	SIGMOD