资源描述：
《mapreduce框架下基于r-树的k-近邻连接算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、软件学报ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,2013,24(8):1836−1851[doi:10.3724/SP.J.1001.2013.04377]http://www.jos.org.cn©中国科学院软件研究所版权所有.Tel/Fax:+86-10-62562563∗MapReduce框架下基于R-树的k-近邻连接算法刘义,景宁,陈荦,熊伟(国防科学技术大学电子科学与工程学院,湖南长沙410073)通讯作者:刘义,E-mail:liu.yi.nudt@gmail.com摘
2、要:针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速构建算法和基于R-树的并行k-近邻连接算法.在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达.在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用R-树索引进行k-近邻连接
3、查询,提高了查询效率.从理论上分析了所提出算法的通信和计算代价.实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值.关键词:云计算;MapReduce;k-近邻连接;空间查询;R-树中图法分类号:TP311文献标识码:A中文引用格式:刘义,景宁,陈荦,熊伟.MapReduce框架下基于R-树的k-近邻连接算法.软件学报,2013,24(8):1836−1851.http://www.jos.org.cn/1000-9825/4377.htm英文引用格式:LiuY,JingN,C
4、henL,XiongW.Algorithmforprocessingk-nearestjoinbasedonR-treeinMapReduce.RuanJianXueBao/JournalofSoftware,2013,24(8):1836−1851(inChinese).http://www.jos.org.cn/1000-9825/4377.htmAlgorithmforProcessingk-NearestJoinBasedonR-TreeinMapReduceLIUYi,JINGNing,CHENLuo,XIONGWei(CollegeofElectronicS
5、cienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)Correspondingauthor:LIUYi,E-mail:liu.yi.nudt@gmail.comAbstract:Toacceleratethek-nearestneighborjoin(knnJ)queryforlargescalespatialdata,thestudypresentsaknnJbasedonR-treeinMapReduce.First,theresearchusesthefor
6、malizationofindependentparallelismandsequentialsynchronization(IPSS)computationtoabstractMapReduceparallelprogrammodel.Next,basedonthisparallelmodelabstraction,thispaperproposesefficientalgorithmsforbulkbuildingR-treeandperformingknnJquerybasedontheconstructedR-treerespectively.Intheproc
7、essofbulkbuildingR-tree,asamplingalgorithmisprovidedtodeterminethespatialpartitionfunctionrapidly,whichmaketheprocessofbuildingR-treeconformtoIPSSmodelandcanbeexpressedeasilyinMapReduce.IntheprocessofknnJquery,theknnexpandedboundingboxisintroducedtolimittheknnqueryrangean
