Hits:

Indexed by:期刊论文

Date of Publication:2016-03-01

Journal:JOURNAL OF SUPERCOMPUTING

Included Journals:SCIE、EI

Volume:72

Issue:3

Page Number:1179-1200

ISSN No.:0920-8542

Key Words:MapReduce; Similarity join; Data set partition; Redundancy

Abstract:Given a massive set of records, similarity join is to find pairs of records with similarity score greater than a threshold. In this paper, we address the problem of scaling up similarity join for general metric distance functions using MapReduce. First, we propose a novel index structure, Similarity Join Tree (SJT), which partitions data based on the underlying data distribution, and distributes similar records to the same group. Different from existing approaches, SJT can prune a large number of comparisons within reduce tasks by utilizing the by-product results generated in partitioning data. Then, to avoid the straggler reduce tasks, we design a graph partition algorithm by extending the well known Fiduccia-Mattheyses algorithm which can ensure load balancing while minimizing communication cost and redundancy in all reduce tasks. Experimental results using real data sets show that our approach is more effective and scalable compared to state-of-the-art algorithms.