Parallel set similarity join on big data based on Locality-Sensitive Hashing

摘要

Due to the huge amount of involved data and time-consuming process of join operations, the exact-match joins are rarely used for big data. The most common alternative for exact-match joins are similarity joins which find similar pairs of records. Set similarity join (SSJ) is defined as join of very large tables based on similarity of a set of their attributes, which is called join attributes. To operate the similarity join of two large tables based on their join attributes, the similarity of the values of the join attributes is specified using an appropriate similarity function, and then, the values pairs which their similarity is higher than a certain threshold, are selected as candidates for join in case of similarity. In this paper, a parallel set similarity join method is introduced using the MapReduce programming model. The proposed method uses Locality Sensitive Hashing (LSH) techniques to decrease the number of required comparisons for calculating the similarity of the sets. The performance of the proposed method has been compared with the best previous similarity join methods on real and synthetic datasets in terms of time. The experimental results show that the proposed method works faster than the former methods.