{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:42:24Z","timestamp":1788482544467,"version":"build-2803163510"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>Nearest neighbor search (NNS) is fundamental for high-dimensional space retrieval and impacts various fields, such as pattern recognition, information retrieval, recommendation systems, and vector database management. Among existing NNS methods, graph-based methods often excel in query accuracy and efficiency. However, these methods face significant challenges, including high construction costs and difficulties with dynamic data updates. Recent efforts have focused on combining graph methods with hashing, quantization, and tree-based approaches to address these issues, but problems with large index sizes and update performance remain unresolved. In response, this paper proposes GTI, a novel, lightweight, and dynamic graph-based tree index for high-dimensional NNS. GTI constructs a tree index built across the entire dataset and employs a lightweight graph index at the level 1 of the tree to significantly reduce graph construction costs. It also features effective data insertion and deletion algorithms that enable logarithmic real-time updates. Additionally, we have developed an effective NNS algorithm for GTI, which not only achieves approximate search performance on par with SOTA graph-based methods but also supports exact NNS. Extensive experiments on six real-world datasets demonstrate that GTI achieves an approximately 10\u00d7 improvement in update efficiency compared to SOTA tree-based methods, while achieving search effectiveness comparable to SOTA approximate NNS methods. These results underscore the potential of GTI for effective application in dynamic and evolving scenarios.<\/jats:p>","DOI":"10.14778\/3717755.3717760","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:51:49Z","timestamp":1747756309000},"page":"986-999","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["GTI: Graph-Based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces"],"prefix":"10.14778","volume":"18","author":[{"given":"Ruiyao","family":"Ma","sequence":"first","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yifan","family":"Zhu","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[{"name":"Singapore Management University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Congcong","family":"Ge","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611537"},{"key":"e_1_2_1_2_1","volume-title":"Datasets for approximate nearest neighbor search.","author":"Amsaleg Laurent","year":"2010","unstructured":"Laurent Amsaleg and Herv\u00e9 Jegou. 2010. Datasets for approximate nearest neighbor search. Retrieved from http:\/\/corpus-texmex.irisa.fr\/ (2010)."},{"key":"e_1_2_1_3_1","volume-title":"Million Song Dataset Benchmarks.","year":"2011","unstructured":"Anon. 2011. Million Song Dataset Benchmarks. Retrieved from http:\/\/www.ifs.tuwien.ac.at\/mir\/msd\/ (2011)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204034"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583166"},{"key":"e_1_2_1_7_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\/93605.98741"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143857"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357776"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the SecondWorkshop on Very Large Digital Libraries.","author":"Bolettieri Paolo","year":"2009","unstructured":"Paolo Bolettieri, Andrea Esuli, Fabrizio Falchi, Claudio Lucchese, Raffaele Perego, and Fausto Rabitti. 2009. Enabling content-based image retrieval in very large digital libraries. In Proceedings of the SecondWorkshop on Very Large Digital Libraries."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Tolga Bozkaya and Z. Meral \u00d6zsoyoglu. 1997. Distance-Based Indexing for High-Dimensional Metric Spaces. In SIGMOD. 357\u2013368.","DOI":"10.1145\/253262.253345"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328959"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0606-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_15_1","volume-title":"Jensen","author":"Chen Lu","year":"2023","unstructured":"Lu Chen, Yunjun Gao, Xuan Song, Zheng Li, Yifan Zhu, Xiaoye Miao, and Christian S. Jensen. 2023. Indexing Metric Spaces for Exact Similarity Search. ACM Comput. Surv. 55, 6 (2023), 128:1\u2013128:39."},{"key":"e_1_2_1_16_1","volume-title":"SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NIPS. 5199\u20135212.","author":"Chen Qi","year":"2021","unstructured":"Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. In NIPS. 5199\u20135212."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137653"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406113"},{"key":"e_1_2_1_19_1","volume-title":"M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB. 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. In VLDB. 426\u2013435."},{"key":"e_1_2_1_20_1","unstructured":"Intel Corporation. 2023. Intel(R) Xeon(R) E Processors. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/products\/details\/processors\/xeon\/e.html (2023)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Wei Dong Moses Charikar and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577\u2013586.","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503594"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547308"},{"key":"e_1_2_1_25_1","first-page":"23","article-title":"Query by Image and Video Content","volume":"28","author":"Flickner Myron","year":"1995","unstructured":"Myron Flickner, Harpreet S. Sawhney, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, David Steele, and Peter Yanker. 1995. Query by Image and Video Content: The QBIC System. Computer 28, 9 (1995), 23\u201332.","journal-title":"The QBIC System. Computer"},{"key":"e_1_2_1_26_1","volume-title":"EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR abs\/1609.07228","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai. 2016. EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. CoRR abs\/1609.07228 (2016)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3067706"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3303753.3303754"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.240"},{"key":"e_1_2_1_30_1","unstructured":"Aristides Gionis Piotr Indyk and Rajeev Motwani. 1999. Similarity Search in High Dimensions via Hashing. In VLDB. 518\u2013529."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397243"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD. 47\u201357.","DOI":"10.1145\/971697.602266"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41062-8_3"},{"key":"e_1_2_1_34_1","volume-title":"Soliman","author":"Ilyas Ihab F.","year":"2008","unstructured":"Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40, 4 (2008), 11:1\u201311:58."},{"key":"e_1_2_1_35_1","volume-title":"Neighborhood Graph and Tree for Indexing Highdimensional Data","author":"Iwasaki Masajiro","year":"2015","unstructured":"Masajiro Iwasaki. 2015. Neighborhood Graph and Tree for Indexing Highdimensional Data. Yahoo Japan Corporation. Retrieved August 22 (2015), 2020."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2302018"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/GC46384.2019.00018"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275366.3284968"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00619-4"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489506"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397240"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_1_46_1","volume-title":"Harsha Vardhan Simhadri, and Yihan Sun","author":"Manohar Magdalen Dobson","year":"2024","unstructured":"Magdalen Dobson Manohar, Zheqi Shen, Guy Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. 2024. ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms. In SIGPLAN. 270\u2013285."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45442-5_34"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Kyriakos Mouratidis Keming Li and Bo Tang. 2021. Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size. In SIGMOD. 1317\u20131330.","DOI":"10.1145\/3448016.3457299"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204031"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2019.106970"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings (Informatik-Fachberichte)","volume":"136","author":"Ooi Beng Chin","year":"1987","unstructured":"Beng Chin Ooi. 1987. Spatial kd-Tree: A Data Structure for Geographic Database. In Datenbanksysteme in B\u00fcro, Technik und Wissenschaft, GI-Fachtagung, Darmstadt, 1.-3. April 1987, Proceedings (Informatik-Fachberichte), Vol. 136. 247\u2013258."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00864-x"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"James Jie Pan Jianguo Wang and Guoliang Li. 2024. Vector Database Management Techniques and Systems. In SIGMOD. 597\u2013604.","DOI":"10.1145\/3626246.3654691"},{"key":"e_1_2_1_54_1","volume-title":"Franklin","author":"Paparrizos John","year":"2022","unstructured":"John Paparrizos, Ikraduya Edian, Chunwei Liu, Aaron J. Elmore, and Michael J. Franklin. 2022. Fast Adaptive Similarity Search through Variance-Aware Quantization. In ICDE. 2969\u20132983."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588908"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Badrul Munir Sarwar George Karypis Joseph A. Konstan and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In WWW. 285\u2013295.","DOI":"10.1145\/371920.372071"},{"key":"e_1_2_1_57_1","unstructured":"Patrick Sch\u00e4fer and Mikael H\u00f6gqvist. 2012. SFA: a symbolic fourier approximation and index for similarity search in high dimensional datasets. In EDBT. 516\u2013527."},{"key":"e_1_2_1_58_1","unstructured":"Harsha Vardhan Simhadri George Williams Martin Aum\u00fcller Matthijs Douze Artem Babenko Dmitry Baranchuk Qi Chen Lucas Hosseini Ravishankar Krishnaswamny Gopal Srinivasa et al. 2022. Results of the NeurIPS'21 challenge on billion-scale approximate nearest neighbor search. In NIPS. 177\u2013189."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424580"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536206.2536208"},{"key":"e_1_2_1_62_1","first-page":"3","article-title":"Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions","volume":"46","author":"Wang Zeyu","year":"2023","unstructured":"Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph- and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions. IEEE Data Eng. Bull. 46, 3 (2023), 3\u201321.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"Zijie J Wang and Duen Horng Chau. 2024. MeMemo: On-device Retrieval Augmentation for Private and Personalized Text Generation. In SIGIR. 2765\u20132770.","DOI":"10.1145\/3626772.3657662"},{"key":"e_1_2_1_64_1","unstructured":"Roger Weber Hans-J\u00f6rg Schek and Stephen Blott. 1998. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In VLDB. 194\u2013205."},{"key":"e_1_2_1_65_1","unstructured":"Yair Weiss Antonio Torralba and Robert Fergus. 2008. Spectral Hashing. In NIPS. 1753\u20131760."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613166"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2880215"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588715"},{"key":"e_1_2_1_69_1","volume-title":"Rundensteiner","author":"Zhang Huayi","year":"2020","unstructured":"Huayi Zhang, Lei Cao, Yizhou Yan, Samuel Madden, and Elke A. Rundensteiner. 2020. Continuously Adaptive Similarity Search. In SIGMOD. 2601\u20132616."},{"key":"e_1_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Yunan Zhang Shige Liu and Jianguo Wang. 2024. Are There Fundamental Limitations in Supporting Vector Data Management in Relational Databases? A Case Study of PostgreSQL. In ICDE. 3640\u20133653.","DOI":"10.1109\/ICDE60146.2024.00280"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594527"},{"key":"e_1_2_1_72_1","doi-asserted-by":"crossref","unstructured":"Chun Jiang Zhu Tan Zhu Haining Li Jinbo Bi and Minghu Song. 2019. Accelerating Large-Scale Molecular Similarity Search through Exploiting High Performance Computing. In BIBM. 330\u2013333.","DOI":"10.1109\/BIBM47256.2019.8982950"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654945"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0442-5"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3717755.3717760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:19:15Z","timestamp":1747757955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3717755.3717760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":74,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.14778\/3717755.3717760"],"URL":"https:\/\/doi.org\/10.14778\/3717755.3717760","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"2025-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}