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

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

1 Scopus Citations
View graph of relations

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationProceedings - International Conference on Data Engineering
PublisherIEEE Computer Society
Pages29-30
ISBN (Print)9781509065431
Publication statusPublished - 16 May 2017

Publication series

Name
ISSN (Print)1084-4627

Conference

Title33rd IEEE International Conference on Data Engineering, ICDE 2017
PlaceUnited States
CitySan Diego
Period19 - 22 April 2017

Abstract

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.

Citation Format(s)

A generic method for accelerating LSH-based similarity join processing (Extended abstract). / Yu, Chenyun; Nutanong, Sarana; Li, Hangyu; Wang, Cong; Yuan, Xingliang.

Proceedings - International Conference on Data Engineering. IEEE Computer Society, 2017. p. 29-30 7929917.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review