Stanford InfoLab Publication Server

Fuzzy Joins Using MapReduce

Afrati, Foto N. and Das Sarma, Anish and Menestrina, David and Parameswaran, Aditya and Ullman, Jeffrey D. Fuzzy Joins Using MapReduce. Technical Report. Stanford InfoLab.




Fuzzy/similarity joins have been widely studied in the research community and extensively used in real-world applications. This paper proposes and evaluates several algorithms for finding all pairs of elements from an input set that meet a similarity threshold. The computation model is a single MapReduce job. Because we allow only one MapReduce round, the Reduce function must be designed so a given output pair is produced by only one task; for many algorithms, satisfying this condition is one of the biggest challenges. We break the cost of an algorithm into three components: the execution cost of the mappers, the execution cost of the reducers, and the communication cost from the mappers to reducers. The algorithms are presented first in terms of Hamming distance, but extensions to edit distance and Jaccard distance are shown as well. We find that there are many different approaches to the similarity-join problem using MapReduce, and none dominates the others when both communication and reducer costs are considered. Our cost analyses enable applications to pick the optimal algorithm based on their communication, memory, and cluster requirements.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:similarity join, map reduce, parallel, hamming, edit distance, jaccard similarity
ID Code:1006
Deposited By:Aditya Parameswaran
Deposited On:19 Jul 2011 21:55
Last Modified:19 Jul 2011 21:55

Download statistics

Repository Staff Only: item control page