Fuzzy Joins Using MapReduce
- 1 April 2012
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 498-509
- https://doi.org/10.1109/icde.2012.66
Abstract
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.Keywords
This publication has 18 references indexed in Scilit:
- Processing theta-joins using MapReducePublished by Association for Computing Machinery (ACM) ,2011
- On scheduling in map-reduce and flow-shopsPublished by Association for Computing Machinery (ACM) ,2011
- Large scale Hamming distance query processingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Document Similarity Self-Join with MapReducePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2010
- A Model of Computation for MapReducePublished by Society for Industrial & Applied Mathematics (SIAM) ,2010
- Binary and Ternary Linear Quasi-Perfect Codes With Small DimensionsIEEE Transactions on Information Theory, 2008
- Efficient similarity joins for near duplicate detectionPublished by Association for Computing Machinery (ACM) ,2008
- Pairwise document similarity in large collections with MapReducePublished by Association for Computational Linguistics (ACL) ,2008
- A Primitive Operator for Similarity Joins in Data CleaningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- On the Nonexistence of Perfect Codes over Finite FieldsSIAM Journal on Applied Mathematics, 1973