基于MapReduce的空间数据RkNN算法研究

《基于MapReduce的空间数据RkNN算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于MapReduce的空间数据RkNN算法研究AnovelSpatialDataRkNNalgorithmbasedonMapReduce作者姓名：奎堡学科、专业：让簋扭丕统结掏学号：20109214指导教9币：奎悫毯一．完成日期：2Q13-一04-25大连理工大学DaliaJlUniversityofTechnology大连理工大学学位论文独创性声明作者郑重声明．o所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不

2、包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：基王№卫基曼堡坠曼星鲍空闽数量堡垒堕翌簋洼丑窥作者签名：銮趋一一日期：丝!!年—丘月—丘日大连理工大学硕士学位论文摘要近几年，随着移动互联网技术和地理信息技术的发展，基于位置服务应用逐渐兴起，从而使得空间定位信息的数据量呈现以指数级增长。而在地理位置信息相关的空间数据查询中，RkNN(Re

3、versekNearestNeighbor，反最近邻)查询问题是通过返回所给查询点周围的对象中，以该查询点作为其kNN(kNearestNeighbor，最近邻)的所有对象的集合，其在多种数据挖掘应用中备受关注。同样传统的RkNN方法也己难以满足迅猛增长的数据速度以及用户们的大规模实时查询要求。本文将传统的RkNN算法与MapReduce分布式框架相结合，分析如何解决大规模空问数据的分布式RkNN查询问题。MapReduce是2004年由谷歌公司提出的一个用来进行并行处理和生成大数据集的模型，而Ma

4、pReduce框架作为分布式计算中的典型的离线计算框架，很难实现实时性计算效果。因此，本文采用了离线和在线相结合的系统模型，利用MapReduce框架离线完成倒排网格索引的创建和更新工作，同时结合在线计算方法返回R心Ⅲ查询结果。文中首先提出基于大规模空间数据集上的倒排网格索引的暴力RkNN查询算法—BaSic．MRkNN算法；接下来提出对此算法的优化算法一延迟Lazy．MRkNN查询算法和增量式Eage卜MRkNN查询算法。为了减少网络和磁盘I／O开销，在过滤过程中利用了一些剪枝规则来提高本文提出的

5、分布式算法性能。此外，通过在32个节点的集群上对模拟数据集和真实数据集的大量实验表明，本文提出的基本算法在与泰森多边形分布式RkNN查询算法相比时能提速50％以上。此外，两种优化算法均优于基本算法，Eager．MRkNN算法比较适合处理密集型数据，而Lazy．MRkNN算法比较适合处理稀疏型数据。关键词：RkNN查询；MapReduce；分布式计算；空间数据AnovelSpatialDataRkNNalgorithmbasedOilMapReduceAbstractInrecentyears，wit

6、hthedevelopmentofmobilecommunicationtechnologyandgeographicinformationtechnology，location-basedspatialdatapresentitsexponentialgrowth．Amongthelocation-basedspatialdataqueries，RkNN(ReversekNearestNeighbor)queryisoneofthemostpopulardataminingapplications

7、indifferentfields．TheresultofRkNNqueryreturnstheobjectsaroundthequerypoint，whichcontainsqastheirkNN(kNearestNeighbor)．However．theexistingRkNNmethodshavebeendifficulttomeettherapidgrowthofdataspeedandreal-timequeryrequirementsfromusers．Inthisthesis．weco

8、mbinethetraditionalRkNNalgorithmandtheMapReducedistributedframeworktoanalyzehowtosolvethelarge·scalespatialdataRkNNquery．MapReduceisamodelproposedbyGooglein2004，whichisusedforparallelprocessingandgeneratinglargedatasets．WhileMapRduceiso