Fast & scalable distributed set similarity joins for big data analytics

Chuitian Rong, Chunbin Lin, Yasin Silva, Jianguo Wang, Wei Lu, Xiaoyong Du

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 Scopus citations


Set similarity join is an essential operation in big data analytics, e.g., data integration and data cleaning, that finds similar pairs from two collections of sets. To cope with the increasing scale of the data, distributed algorithms are called for to support large-scale set similarity joins. Multiple techniques have been proposed to perform similarity joins using MapReduce in recent years. These techniques, however, usually produce huge amounts of duplicates in order to perform parallel processing successfully as MapReduce is a shared-nothing framework. The large number of duplicates incurs on both large shuffle cost and unnecessary computation cost, which significantly decrease the performance. Moreover, these approaches do not provide a load balancing guarantee, which results in a skewness problem and negatively affects the scalability properties of these techniques. To address these problems, in this paper, we propose a duplicate free framework, called FS-Join, to perform set similarity joins efficiently by utilizing an innovative vertical partitioning technique. FS-Join employs three powerful filtering methods to prune dissimilar string pairs without computing their similarity scores. To further improve the performance and scalability, FS-Join integrates horizontal partitioning. Experimental results on three real datasets show that FS-Join outperforms the state-of-Theart methods by one order of magnitude on average, which demonstrates the good scalability and performance qualities of the proposed technique.

Original languageEnglish (US)
Title of host publicationProceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781509065431
StatePublished - May 16 2017
Event33rd IEEE International Conference on Data Engineering, ICDE 2017 - San Diego, United States
Duration: Apr 19 2017Apr 22 2017

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other33rd IEEE International Conference on Data Engineering, ICDE 2017
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Fast & scalable distributed set similarity joins for big data analytics'. Together they form a unique fingerprint.

Cite this