Efficient locality-sensitive hashing over high-dimensional streaming data

Hao Wang, Chengcheng Yang, Xiangliang Zhang, Xin Gao

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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
StatePublished - Sep 17 2020

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): BAS/1/1624
Acknowledgements: The authors would like to thank the editor and anonymous reviewers for their valuable suggestions and comments. This work was funded in part by the Center of Excellence for NEOM Research at KAUST, REI/1/4178-01-01, the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research (OSR) under award numbers BAS/1/1624-01, REI/1/0018-01-01, REI/1/4216-01-01, REI/1/4437-01-01, and REI/1/4473-01-01.


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

Cite this