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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

LH-DPT: An Update Efficient Index for High-Dimensional Approximate Nearest Neighbor Search

  • Xinrui Guo,
  • Xianping Meng,
  • Na Guo

摘要

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.