DET-LSH: A Locality-sensitive Hashing Scheme With Dynamic Encoding Tree For Approximate Nearest Neighbor Search
2024 · Jiuqi Wei, Botao Peng, Xiaodong Lee, et al.
Abstract
Locality-sensitive hashing (LSH) is a well-known solution for approximate nearest neighbor (ANN) search in high-dimensional spaces due to its robust theoretical guarantee on query accuracy. Traditional LSH-based methods mainly focus on improving the efficiency and accuracy of the query phase by designing different query strategies, but pay little attention to improving the efficiency of the indexing phase. They typically fine-tune existing data-oriented partitioning trees to index data points and support their query strategies. However, their strategy to directly partition the multi-dimensional space is time-consuming, and performance degrades as the space dimensionality increases. In this paper, we design an encoding-based tree called Dynamic Encoding Tree (DE-Tree) to improve the indexing efficiency and support efficient range queries based on Euclidean distance. Based on DE-Tree, we propose a novel LSH scheme called DET-LSH. DET-LSH adopts a novel query strategy, which performs rang
Authors
(none)
Tags
Stats
Related papers
- Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
- Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
- Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
- PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
- Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00
- Drawbacks And Proposed Solutions For Real-time Processing On Existing State-of-the-art Locality Sensitive Hashing Techniques (2019)0.00
- Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
- Distance-sensitive Hashing (2017)8.82