你好,游客 登录 注册 发布搜索
背景:
阅读新闻

[硕士论文]基于MapReduce的大数据连接算法的设计与优化

[日期:2014-10-23] 来源:CNKI  作者: 张常淳 [字体: ]

基于MapReduce的大数据连接算法的设计与优化

中国科学技术大学   张常淳 

本文在深入研究和总结相关领域已有成果的基础上,围绕基于MapReduce的数据连接算法效率优化问题,主要开展了以下的研究工作: 首先,本文提出了基于MapReduce的Maxdiff直方图的高效建立算法,包括准确算法和近似算法。Maxdiff直方图可以准确地评估数据集内的数据分布情况,例如可以提供数据倾斜的情况或者数据集之间连接属性的连接选择率等重要信息,为后文连接算法的优化做了一个基础工作。 其次,本文提出了基于BloomFilter的等值连接算法,核心思想是利用BloomFilter减少map和reduce之间网络传输量从而提高等值连接算法的效率。为此,首先提出了基于MapReduce的BloomFilter高效建立算法;其次提出了基于BloomFilter的等值连接算法,包括两表等值连接和多表等值连接;最后基于磁盘I/O和网络I/O建立了等值连接算法代价模型,用以选择基于MapReduce的最优等值连接效率方案。 再次,本文提出了针对数据倾斜的两表等值连接算法和多表等值连接算法。针对两表等值连接,优化了数据集中的一个或者几个数据出现过多时的连接算法效率。对于多表等值连接,采用基于值域分区(range partition)的方法,优化了用一轮MapReduce任务完成数据倾斜的多表连接算法效率。 最后,本文提出了基于MapReduce的多表任意连接算法。首先提出了用一轮MapReduce来完成多表任意连接算法(SEJ),核心思想是利用拉格朗日乘法来最优化网络传输量,同时采用随机化方法保证reduce端的负载均衡;然后基于算法SEJ和多表连接算法的代价模型,提出了一个动态规划算法生成基于MapReduce的多表任意连接的最优化连接方案。

 

基于MapReduce的大数据连接算法的设计与优化

收藏 推荐 打印 | 录入:574107552 | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款