分布式平台下基于开销估算的多数据集连接方法-计算机软件与理论专业论文.docxVIP

独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 必威体育官网网址□ ，在 年解密后适用本授权书。 本论文属于  不必威体育官网网址? （请在以上方框内打“√”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 华中科技大学硕士学位论文 华 中 科 技 大 学 硕 士 学 位 论 文 I I 摘要 分布式计算的发展为大数据的分析和处理提供了一个新的平台。MapReduce 是一种能够在分布式系统中实现大规模数据并行运算的分布式计算框架。但是 MapReduce 自身的不足限制了它处理多数据集连接的能力。如何改进现有的利用 MapReduce 处理多数据集连接的方法，提高 MapReduce 处理数据集连接的效率， 对于提高数据的查询、分析效率，更好地支持大数据的分析处理具有重要的意义。 分析 MapReduce 计算框架中 Map 阶段和 Reduce 阶段的数据处理过程，在现 有连接开销模型的基础上，细化 Map 阶段和 Reduce 阶段中的数据排序、压缩等 过程，加入 map 函数和 reduce 函数部分的计算开销。给出利用概率分布函数估算 连接结果数据量的方法，使模型能更好地服务于连接计划的规划。 以开销估算模型为基础，设计一个结合贪心和动态规划策略的多数据集连接 方法。首先利用预等值连接减少参与非等值连接的数据集的数据量，降低后续处 理非等值连接所需的开销；其次，利用 ThetaJoin 分步连接和二路 ThetaJoin 连接 组处理所有非等值连接；最后，利用贪心和动态规划将等值连接分解成多个子模 块，并为每个子模块选择合适的连接方案。这种启发式的连接方法利用开销模型 分析现有连接方法在处理不同连接场景时的优劣，将任务进行分解，为每个子任 务选择合适的连接方法，实现以减少局部连接的开销来提高整个连接任务效率的 目的。 设计不同的连接场景，在搭建的 Hadoop 并行计算平台上对多种不同的连接 方法进行实验。实验结果表明，设计的连接方法比其余的连接方法更能适应不同 的连接场景，具有更高的效率，更好的有效性。 关键词：分布式，连接计划，开销模型，贪心，动态规划 II II Abstract Distributed computing provides a new platform for big data analysis and processing. MapReduce is an important programming model, it is often used for processing large datasets in a parallel or distributed computing environment. However, because of some disadvantages of this programming model, it is inefficient to perform join operations in MapReduce when mulitiple datasets are involved. How to improve the existing methods which use MapReduce to process multiple datasets joins, has significance to improve the efficiency of data query and analysis. Considering the time cost of join processing, sorting and compression in a MapReduce job, a time cost evaluation model is extended for calculating the time cost of a MapReduce job. And in order to make the model more useful, how to