点击次数：

论文类型：期刊论文

发表时间：2016-03-01

发表刊物：JOURNAL OF SUPERCOMPUTING

收录刊物：SCIE、EI

卷号：72

期号：3

页面范围：1179-1200

ISSN号：0920-8542

关键字：MapReduce; Similarity join; Data set partition; Redundancy

摘要：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.