A Generic Method for Accelerating LSH-Based Similarity Join Processing
- 13 December 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 29 (4) , 712-726
Abstract
Locality sensitive hashing (LSH) is an efficient method for solving the problem of approximate similarity search in highdimensional spaces. Through LSH, a high-dimensional similarity join can be processed in the same way as hash join, making the cost of joining two large datasets linear. By judicially analyzing the properties of multiple LSH algorithms, we propose a generic method to speed up the process of joining two large datasets using LSH. The crux of our method lies in the waywhich we identify a set of representative points to reduce the number of LSH lookups. Theoretical analyzes show that our proposed method can greatly reduce the number of lookup operations and retain the same result accuracy compared to executing LSH lookups for every query point. Furthermore, we demonstrate the generality of our method by showing that the same principle can be applied to LSH algorithms for three different metrics: the Euclidean distance (QALSH), Jaccard similarity measure (MinHash), and Hamming distance (sequence hashing). Results from experimental studies using real datasets confirm our error analyzes and show significant improvements of our method overthe state-of-the-art LSH method: to achieve over 0.95 recall, we only need to operate LSH lookups for at most 15 percent of the query points.Keywords
Funding Information
- CityU (7200387)
- ITF (ITS/307/15)
This publication has 24 references indexed in Scilit:
- Query-aware locality-sensitive hashing for approximate nearest neighbor searchProceedings of the VLDB Endowment, 2015
- Mining of Massive Datasets2014
- NCBI Reference Sequences (RefSeq): current status, new features and genome annotation policyNucleic Acids Research, 2011
- Efficient k-nearest neighbor graph construction for generic similarity measures2011
- Provably Sensitive Indexing Strategies for Biosequence Similarity SearchJournal of Computational Biology, 2003
- GESS2001
- Epsilon grid order2001
- Min-wise Independent Permutations: Theory and Practice2000
- Approximating the minimum maximal independence numberInformation Processing Letters, 1993
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963