LH-DPT: An Update Efficient Index for High-Dimensional Approximate Nearest Neighbor Search
摘要
Large-scale high-dimensional vector indexing with fast update capabilities plays a crucial role in real-time systems. However, existing indexing methods have certain limitations in terms of updates. Graph-based indexes suffer from slow construction and update speeds, tree-based indexes are not well-suited for high-dimensional datasets, Locality sensitive hashing (LSH)-based indexes support efficient updates but demonstrate suboptimal search performance. In this paper, we propose an index that combines learned LSH with tree-based structures. We employ a neural network to approximate the LSH computation process and design a dimension-partitioning tree (DPT) with an insertion table to index the hash-reduced data. We also develop insertion and query algorithms for DPT. Learned LSH accelerates updates by reducing the computation time required for high-dimensional vector multiplications in LSH, while DPT compensates for LSH’s accuracy limitations. Furthermore, its construction method, which avoids directly partitioning the space, further enhances the efficiency of data insertion and updates. Based on these two methods, we introduce Learned locality-sensitive Hashing Dimension-Partitioning Tree (LH-DPT) for approximate nearest neighbor search in large-scale high-dimensional vector spaces with frequent updates. Extensive experiments demonstrate that LH-DPT achieves comparable query accuracy to other state-of-the-art LSH methods on both real and synthetic datasets, while achieving 2 \(\times \) speedup in index construction, 2.2 \(\times \) speedup in data updates and 1.6 \(\times \) speedup in query processing.