Efficient locality-sensitive hashing over high-dimensional streaming data

Hao Wang, Chengcheng Yang, Xiangliang Zhang, Xin Gao

Research output: Contribution to journalArticlepeer-review

Abstract

Approximate nearest neighbor (ANN) search in high-dimensional spaces is fundamental in many applications. Locality-sensitive hashing (LSH) is a well-known methodology to solve the ANN problem. Existing LSH-based ANN solutions typically employ a large number of individual indexes optimized for searching efficiency. Updating such indexes might be impractical when processing high-dimensional streaming data. In this paper, we present a novel disk-based LSH index that offers efficient support for both searches and updates. The contributions of our work are threefold. First, we use the write-friendly LSM-trees to store the LSH projections to facilitate efficient updates. Second, we develop a novel estimation scheme to estimate the number of required LSH functions, with which the disk storage and access costs are effectively reduced. Third, we exploit both the collision number and the projection distance to improve the efficiency of candidate selection, improving the search performance with theoretical guarantees on the result quality. Experiments on four real-world datasets show that our proposal outperforms the state-of-the-art schemes.
Original languageEnglish (US)
JournalNeural Computing and Applications
DOIs
StatePublished - Sep 17 2020

Fingerprint Dive into the research topics of 'Efficient locality-sensitive hashing over high-dimensional streaming data'. Together they form a unique fingerprint.

Cite this