A generic method for accelerating LSH-based similarity join processing (extended abstract)

Chenyun Yu, Sarana Nutanong, Hangyu Li, Cong Wang, Xingliang Yuan

Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

1 Citation (Scopus)


Locality sensitive hashing (LSH) is an efficient method for solving the problem of approximate similarity search in high-dimensional 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 accelerate the process of joining two large datasets using LSH. The crux of our method lies in the way we identify a set of representative points to reduce the number of LSH lookups. Theoretical analyses 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 analyses and show significant improvements of our method over the state-of-The-Art LSH method: To achieve over 0.95 recall, we only need to operate LSH lookups for at most 15% of the query points.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
Subtitle of host publication19-22 April 2017, San Diego, California, USA
EditorsYannis Papakonstantinou, Yanlei Diao
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages2
ISBN (Electronic)9781509065431
Publication statusPublished - 2017
Externally publishedYes
EventIEEE International Conference on Data Engineering 2017 - Hilton San Diego Resort and Spa in Mission Bay, San Diego, United States of America
Duration: 19 Apr 201722 Apr 2017
Conference number: 33rd
http://icde2017.sdsc.edu/ (Conference website)
https://ieeexplore.ieee.org/xpl/conhome/7929494/proceeding (Proceedings)


ConferenceIEEE International Conference on Data Engineering 2017
Abbreviated titleICDE 2017
Country/TerritoryUnited States of America
CitySan Diego
Internet address

Cite this