Metric Similarity Joins Using MapReduce
Metric Similarity Joins Using MapReduce
复制标题
DOI：
10.1109/tkde.2016.2631599
复制
发表时间：
2017-03
影响因子：
8.9
通讯作者：
Gang Chen;Keyu Yang;Lu Chen;Yunjun Gao;Baihua Zheng;Chun Chen
中科院分区：
文献类型：
--
作者：
Gang Chen;Keyu Yang;Lu Chen;Yunjun Gao;Baihua Zheng;Chun Chen
给定两个对象集Q和O，度量相似性连接根据一定的标准找到相似的对象对。此操作在数据清理和数据挖掘中有广泛的应用，仅举几例。然而，如今快速增长的数据量挑战传统的度量相似性连接方法，因此，需要一种分布式方法。在本文中，我们采用了流行的分布式框架，即MapReduce，支持可扩展的度量相似连接。为了保证负载均衡，我们提出了两种基于采样的分区方法。一种是利用主元和空间填充曲线映射将数据聚类到一维空间中，然后选择高质量的质心来实现大小相等的分区。另一种是使用KD树划分技术来平均划分数据后的枢轴映射。为了避免不必要的对象对评估，我们提出了一个框架，映射两个涉及的对象集的顺序，其中范围对象过滤，双枢轴过滤，枢轴过滤，和平面扫描技术用于修剪。使用真实的和合成数据集进行的大量实验表明，我们的解决方案明显优于现有的最先进的竞争对手。
Given two object sets Q and O, a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning and data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster the data into one-dimensional space, and then selects high quality centroids to enable equal-sized partitions. The other uses the KD-tree partitioning technique to equally divide the data after the pivot mapping. To avoid unnecessary object pair evaluation, we propose a framework that maps the two involved object sets in order, where the range-object filtering, the double-pivot filtering, the pivot filtering, and the plane sweeping techniques are utilized for pruning. Extensive experiments with both real and synthetic data sets demonstrate that our solutions outperform significantly existing state-of-the-art competitors.