DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search

doi:10.14778/3665844.3665854

	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search
	Wei, Jiuqi 1,2; Peng, Botao 1; Lee, Xiaodong 1; Palpanas, Themis 3
	2024-05-01
发表期刊	PROCEEDINGS OF THE VLDB ENDOWMENT
ISSN	2150-8097
卷号	17 期号:9 页码:2241-2254
摘要	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 multidimensional 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.
DOI	10.14778/3665844.3665854
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China (NSFC)[62202450]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods
WOS记录号	WOS:001308222700010
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39594
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Wei, Jiuqi
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Univ Paris Cite, LIPADE, Paris, France
推荐引用方式 GB/T 7714	Wei, Jiuqi,Peng, Botao,Lee, Xiaodong,et al. DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search[J]. PROCEEDINGS OF THE VLDB ENDOWMENT,2024,17(9):2241-2254.
APA	Wei, Jiuqi,Peng, Botao,Lee, Xiaodong,&Palpanas, Themis.(2024).DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search.PROCEEDINGS OF THE VLDB ENDOWMENT,17(9),2241-2254.
MLA	Wei, Jiuqi,et al."DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search".PROCEEDINGS OF THE VLDB ENDOWMENT 17.9(2024):2241-2254.