基于MapReduce的相似自连接新方法：过滤和内切圆算法

来源：计算机研究与发展杂志2016年第12期北京时间：

作者：鲍广慧,张兆功,李建中,玄萍,

摘要：相似自连接是一个在很多应用领域中很重要的问题.对于海量数据集，MapReduce可以提供一个有效的分布式计算框架，相似自连接操作也同样可以应用在MapReduce框架下.但已有研究工作仍然存在不足，如对于聚集数据区域采用加细划分方法，目的是负载平衡，但不易实现.现有的算法不能有效地完成海量数据集的相似自连接操作.为此提出了2个新颖的基于MapReduce的相似自连接算法，其思想是采用坐标过滤技术，形成有效候选集，以及针对聚集区域采用六边形划分的内切圆算法.过虑技术是在等宽网格划分基础上，利用同一维坐标间的距离差与相似性约束阈值ε进行比较，可以明显地减少候选集的数量，也证明了六边形划分是所有正多边形全覆盖中最优的划分方法.实验结果表明：新方法比其他算法有更高的效率，提高效率80%以上，它能够有效地解决有聚集区域的海量数据集的相似自连接问题.

关键词：海量数据集, 过滤, 相似自连接, 数据划分, Hadoop平台, MapReduce编程模型,