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

发布时间：2017-06-19 07:06

  本文关键词：基于MapReduce的相似自连接新方法:过滤和内切圆算法，由笔耕文化传播整理发布。

【摘要】：相似自连接是一个在很多应用领域中很重要的问题.对于海量数据集,MapReduce可以提供一个有效的分布式计算框架,相似自连接操作也同样可以应用在MapReduce框架下.但已有研究工作仍然存在不足,如对于聚集数据区域采用加细划分方法,目的是负载平衡,但不易实现.现有的算法不能有效地完成海量数据集的相似自连接操作.为此提出了2个新颖的基于MapReduce的相似自连接算法,其思想是采用坐标过滤技术,形成有效候选集,以及针对聚集区域采用六边形划分的内切圆算法.过虑技术是在等宽网格划分基础上,利用同一维坐标间的距离差与相似性约束阈值ε进行比较,可以明显地减少候选集的数量,也证明了六边形划分是所有正多边形全覆盖中最优的划分方法.实验结果表明:新方法比其他算法有更高的效率,提高效率80%以上,它能够有效地解决有聚集区域的海量数据集的相似自连接问题.
【作者单位】： 黑龙江大学计算机科学与技术学院;哈尔滨工业大学计算机科学与技术学院;
【关键词】： 海量数据集 过滤 相似自连接 数据划分 Hadoop平台 MapReduce编程模型
【基金】：国家“九七三”重点基础研究发展计划基金项目(2012CB316200) 国家自然科学基金项目(61302139)~~
【分类号】：TP311.13
【正文快照】： 连接操作(join)是一个很重要的数据库操作,相似自连接是join的一种特殊类型,即对同一数据类型进行相似自连接操作.它在数据分析中扮演很重要的角色:数据清理[1]、相近的文本查重[2]、文件相似性分析[3]和数据挖掘等工作,特别在基于密度的聚类分析中也用到了相似自连接操作的结

  本文关键词：基于MapReduce的相似自连接新方法:过滤和内切圆算法，由笔耕文化传播整理发布。

，

本文编号：461767