基于mapreduce的海量skyline计算研究

《基于mapreduce的海量skyline计算研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于MapReduce的海量Skyline计算研究ResearchofMassiveSkylineComputingBasedonMapReduce学号：2111ZQ曼垒完成日期：2Q!垒!Q墨12鱼大连理工大学DalianUniversityofTechnology大连理工大学学位论文独创性声明作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所

2、做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：基王M垒卫垦璺垦望璺曼鲍连量墨至￥!i旦曼进篡盟窒作者签名：——j二盗坠丝之—一日期：—盟年—￡月三二退大连理工大学硕士学位论文摘要近年来，随着互联网应用的迅速发展和云计算技术的广泛应用，数据存储量呈现爆炸式增长。如何在大规模数据集中找到人们感兴趣的数据，帮助人们做出有效的决断，是一个亟待解决的问题。Skyline计算用于解决多目标决策问题。从已有的研究内容来看，Skyline计算可分为集中式处理和分布式处理。集中式处理的研究相对较为成熟，包括BNL

3、(blocknestedloop)、D&C(divideandconquer)和SFS(sort．filter—skyline)等多种算法。由于大数据的发展，分布式处理尤为重要。MapReduce模型由Google公司提出，该模型具有高容错性和良好的扩展性，适用于数据密集型应用处理。因此，将Skyline计算置于MapReduce模型下运行是一个很好的选择。Skyline计算在MapReduce模型上运行，需要考虑的问题是如何对数据集进行划分。目前已知的划分方法有随机划分、网格划分和基于角度的划分。随机划分简单，但是运行不稳定。网格划分仅适用于低维度

4、数据集。基于角度的划分先将点的坐标投影到超球面上，然后根据超球面坐标对数据集进行划分。使用这种划分在求局部结果集时可以淘汰更多数据，但该划分前的坐标转换较复杂、费时。本文采用基于超平面投影的划分对数据集进行划分。该划分首先将点的坐标投影到超平面上，然后根据超平面坐标对数据集进行划分。这种划分方法继承了基于角度划分的优点，即划分后求出的局部结果集较小，同时弥补了基于角度划分的不足，即该划分前的坐标转换简单、省时。本文提出基于该划分下的Skyline计算算法MR．HPP(MapReducewithhyperplane-projections．basedp

5、artition)，然后从该算法的合并过滤阶段及MapReduce的Shuffle阶段入手，对计算过程进行了优化。为了验证MR-HPP算法的有效性，我们在Hadoop平台下对以上几种划分策略下的算法进行了大量的对比实验，实验结果表明，本文提出的MR．HPP算法具有良好的扩展性、高效性和稳定性。关键词：Skyline计算；大数据；MapReduce；基于超平面投影的划分基于MapReduce的海量Skyline计算研究ResearchofMassiveSkylineComputingBasedonMapReduceAbstractRecently．、析

6、t11therapiddevelopmentofInternetapplicationsandwidespreadapplicationofcloudcomputing，dataisshowingthescaleofexplosivegrowth．Howtofindinterestingdatatohelppeoplemakeeffectivedecisionsisanurgentproblem．Skylinecomputingisusedtosettlemulti-objectivedecision-makingproblems．Skylineco

7、mputingincludescentralizedprocessinganddistributedprocessingfromexistingresearchcontent．Theresearchoncentralizedprocessinghasbeenmature，whichincludesalgorithmofBNL(blocknestedloop)，D&C(divideandconquer)，SFS(sort—filter·skyline)andSOon．Withdevelopmentofbigdata,distributedprocess

8、ingbecomesimportant．TheMapReducemodelproposedbyGoogleh