  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 range queries in multiple independent index DE-Trees
to reduce the probability of missing exact NN points, thereby improving the
query accuracy. Our theoretical studies show that DET-LSH enjoys probabilistic
guarantees on query accuracy. Extensive experiments on real-world datasets
demonstrate the superiority of DET-LSH over the state-of-the-art LSH-based
methods on both efficiency and accuracy. While achieving better query accuracy
than competitors, DET-LSH achieves up to 6x speedup in indexing time and 2x
speedup in query time over the state-of-the-art LSH-based methods. This paper
was published in PVLDB 2024.
