Publication Type
Journal Article
Version
publishedVersion
Publication Date
9-2025
Abstract
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 realtime 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× 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.
Discipline
Graphics and Human Computer Interfaces
Research Areas
Intelligent Systems and Optimization
Areas of Excellence
Digital transformation
Publication
Proceedings of the VLDB Endowment
Volume
18
Issue
4
First Page
986
Last Page
999
ISSN
2150-8097
Identifier
10.14778/3717755.3717760
Publisher
VLDB Endowment
Citation
MA, Ruoyao; ZHU, Yifan; ZHENG, Baihua; CHEN, Lu; GE, Congcong; and GAO, Yunjun.
GTI: Graph-based tree index with logarithm updates for nearest neighbor search in high-dimensional spaces. (2025). Proceedings of the VLDB Endowment. 18, (4), 986-999.
Available at: https://ink.library.smu.edu.sg/sis_research/10353
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://dl.acm.org/doi/10.14778/3717755.3717760