{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T00:06:13Z","timestamp":1756512373032,"version":"3.44.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/3734839.3734860","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:01:06Z","timestamp":1756483266000},"page":"2268-2280","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Wolverine: Highly Efficient Monotonic Search Path Repair for Graph-Based ANN Index Updates"],"prefix":"10.14778","volume":"18","author":[{"given":"Dawei","family":"Liu","sequence":"first","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Bolong","family":"Zheng","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Ziyang","family":"Yue","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Fuhao","family":"Ruan","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[{"name":"Aalborg University"}]}],"member":"320","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_2_1","volume-title":"Mount","author":"Arya Sunil","year":"1993","unstructured":"Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In SODA. 271\u2013280."},{"key":"e_1_2_1_3_1","volume-title":"Lempitsky","author":"Babenko Artem","year":"2016","unstructured":"Artem Babenko and Victor S. Lempitsky. 2016. Efficient Indexing of Billion-Scale Datasets of Deep Descriptors. In CVPR. 2055\u20132063."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Norbert Beckmann Hans-Peter Kriegel Ralf Schneider and Bernhard Seeger. 1990. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In SIGMOD. 322\u2013331.","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_1_6_1","volume-title":"Keogh","author":"Camerra Alessandro","year":"2010","unstructured":"Alessandro Camerra, Themis Palpanas, Jin Shieh, and Eamonn J. Keogh. 2010. iSAX 2.0: Indexing and Mining One Billion Time Series. In ICDM. 58\u201367."},{"key":"e_1_2_1_7_1","volume-title":"M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. PVLDB., 426\u2013435.","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. PVLDB., 426\u2013435."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Kunal Dahiya Deepak Saini Anshul Mittal Ankush Shaw Kushal Dave Akshay Soni Himanshu Jain Sumeet Agarwal and Manik Varma. 2021. DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents. In WSDM. 31\u201339.","DOI":"10.1145\/3437963.3441810"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.1988.754602"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3067706"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Junhao Gan Jianlin Feng Qiong Fang and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting. In SIGMOD. 541\u2013552.","DOI":"10.1145\/2213836.2213898"},{"key":"e_1_2_1_13_1","unstructured":"Tiezheng Ge Kaiming He Qifa Ke and Jian Sun. 2013. Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2946\u20132953."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.240"},{"key":"e_1_2_1_15_1","unstructured":"Kiana Hajebi Yasin Abbasi-Yadkori Hossein Shahbazi and Hong Zhang. 2011. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. In IJCAI. 1312\u20131317."},{"key":"e_1_2_1_16_1","volume-title":"FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722.","author":"Harwood Ben","year":"2016","unstructured":"Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713\u20135722."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2853161"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Piotr Indyk and Rajeev Motwani. 1998. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. In STOC. 604\u2013613.","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_21_1","unstructured":"Herv\u00e9 J\u00e9gou Romain Tavenard Matthijs Douze and Laurent Amsaleg. 2011. Datasets for approximate nearest neighbor search. http:\/\/corpus-texmex.irisa.fr\/."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Yannis Kalantidis and Yannis Avrithis. 2014. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In CVPR. 2329\u20132336.","DOI":"10.1109\/CVPR.2014.298"},{"key":"e_1_2_1_23_1","volume-title":"Tung","author":"Lei Yifan","year":"2020","unstructured":"Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In SIGMOD. 2589\u20132599."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_27_1","unstructured":"Microsoft. 2021. SPACEV1B: A billion-Scale vector dataset for text descriptors. https:\/\/github.com\/microsoft\/SPTAG\/tree\/main\/datasets\/SPACEV1B."},{"key":"e_1_2_1_28_1","volume-title":"Jianye Yang, and Jianliang Xu.","author":"Peng Yun","year":"2023","unstructured":"Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. SIGMOD 1, 1 (2023), 54:1\u201354:27."},{"key":"e_1_2_1_29_1","volume-title":"Hartley","author":"Silpa-Anan Chanop","year":"2008","unstructured":"Chanop Silpa-Anan and Richard I. Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In CVPR. 1\u20138."},{"key":"e_1_2_1_30_1","volume-title":"Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri.","author":"Singh Aditi","year":"2021","unstructured":"Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. CoRR abs\/2105.09613 (2021)."},{"key":"e_1_2_1_31_1","volume-title":"NeurIPS","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS 2019. 24\u201334."},{"key":"e_1_2_1_32_1","volume-title":"Ravishankar Krishnaswamy, and Rohan Kadekodi.","author":"Subramanya Suhas Jayaram","year":"2019","unstructured":"Suhas Jayaram Subramanya, Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, and Rohan Kadekodi. 2019. Rand-NSG: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. In NeurIPS. 13748\u201313758."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735461.2735462"},{"key":"e_1_2_1_34_1","first-page":"39","article-title":"Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions","volume":"46","author":"Tian Yao","year":"2023","unstructured":"Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Databases: Current Research and Future Directions. IEEE Data Eng. Bull. 46, 3 (2023), 39\u201354.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Yao Tian Xi Zhao and Xiaofang Zhou. 2022. DB-LSH: Locality-Sensitive Hashing with Query-based Dynamic Bucketing. In ICDE. 2250\u20132262.","DOI":"10.1109\/ICDE53745.2022.00214"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3295831"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Yuming Xu Hengyu Liang Jin Li Shuotao Xu Qi Chen Qianxi Zhang Cheng Li Ziyue Yang Fan Yang Yuqing Yang Peng Cheng and Mao Yang. 2023. SPFresh: Incremental In-Place Update for Billion-Scale Vector Search. In SOSP. 545\u2013561.","DOI":"10.1145\/3600006.3613166"},{"key":"e_1_2_1_39_1","volume-title":"Jensen","author":"Zheng Bolong","year":"2023","unstructured":"Bolong Zheng, Ziyang Yue, Qi Hu, Xiaomeng Yi, Xiaofan Luan, Charles Xie, Xiaofang Zhou, and Christian S. Jensen. 2023. Learned Probing Cardinality Estimation for High-Dimensional Approximate NN Search. In ICDE. 3209\u20133221."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3377369.3377374"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3734839.3734860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T16:03:47Z","timestamp":1756483427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3734839.3734860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":40,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10.14778\/3734839.3734860"],"URL":"https:\/\/doi.org\/10.14778\/3734839.3734860","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"2025-08-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}