论文部分内容阅读
近年来,随着互联网技术的广泛普及,以博客、社交网络等为代表的新型应用得到了广泛使用,同时伴随着云计算等技术的飞速发展,互联网中的数据正以前所未有的速度增长和积累,大数据已经走入我们的生活。2004年Google提出的MapReduce并行编程环境,已经在大数据处理领域得到了广泛的应用。Yahoo!, Facebook, Amazon等大型互联网公司都纷纷应用MapReduce来处理大数据相关问题,同时,学术界也对MapReduce的相关算法做出了巨大贡献,有效地推动了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的大数据连接算法效率优化问题出发,围绕着等值连接算法效率优化,数据倾斜的连接算法效率优化和θ连接算法效率优化问题进行研究,提出的算法能够有效地提升程序的执行效率,同时为后续的的研究工作给予借鉴和参考。