ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (12): 2847-2857.doi: 10.7544/issn1000-1239.2016.20150794

• 软件技术 • 上一篇    下一篇

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

鲍广慧1,张兆功1,李建中1,2,玄萍1   

  1. 1(黑龙江大学计算机科学与技术学院 哈尔滨 150080); 2(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) (851890784@qq.com)
  • 出版日期: 2016-12-01
  • 基金资助: 
    国家“九七三”重点基础研究发展计划基金项目(2012CB316200);国家自然科学基金项目(61302139)

Novel MapReduce-Based Similarity Self-Join Method: Filter and In-Circle Algorithm

Bao Guanghui1, Zhang Zhaogong1, Li Jianzhong1,2, Xuan Ping1   

  1. 1(School of Computer Science and Technology, Heilongjiang University, Harbin 150080); 2(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Online: 2016-12-01

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

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

Abstract: Similarity self-join is a very important study in many applications. For the massive data sets, MapReduce can provide an effective distributed computing framework, in particular, similarity self-join can be applied on the framework. There are still problems, such as fine partition method, are applied to cluster data area for load balancing, but it is not easy to implement. Existing algorithms cant effectively accomplish similarity self-join operations for the massive data sets. In this paper, we propose two novel algorithms of similarity self-join on the MapReduce framework, and use coordinate-filtering techniques to get the valid candidate sets and use the in-circle method on the hexagon-based partition area. Those coordinate-filtering techniques are based on equal-width grid partition, and adopt the restriction that two points have more distances than two projective points in the same axis, and can drop obviously some candidate set. We also proof that the hexagon-based partition is the best form in all normal partition. Our experimental results demonstrate that the novel method has an advantage over the other join algorithms for cluster data area which improves efficiency over 80%. The algorithm can effectively solve the problem of the similarity self-join for the massive data in cluster data area.

Key words: massive data sets, filter, similarity self-join, data partition, Hadoop platform, MapReduce programming model

中图分类号: