MapReduce框架下基于R-树的k-近邻连接算法  

Algorithm for Processing k-Nearest Join Based on R-Tree in MapReduce

作　　者：刘义[1] 景宁[1] 陈荦[1] 熊伟[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,湖南长沙410073

出　　处：《软件学报》2013年第8期1836-1851,共16页Journal of Software

基　　金：国家自然科学基金(61070035;41271403);国家高技术研究发展计划(863)(2011AA120306;2007AA120402);高等学校博士学科点专项科研基金(20104307110017)

摘　　要：针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速构建算法和基于R-树的并行k-近邻连接算法.在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达.在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用R-树索引进行k-近邻连接查询,提高了查询效率.从理论上分析了所提出算法的通信和计算代价.实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值.To accelerate the k-nearest neighbor join（knnJ） query for large scale spatial data,the study presents a knnJ based on R-tree in MapReduce.First,the research uses the formalization of independent parallelism and sequential synchronization（IPSS） computation to abstract MapReduce parallel program model.Next,based on this parallel model abstraction,this paper proposes efficient algorithms for bulk building R-tree and performing knnJ query based on the constructed R-tree respectively.In the process of bulk building R-tree,a sampling algorithm is provided to determine the spatial partition function rapidly,which make the process of building R-tree conform to IPSS model and can be expressed easily in MapReduce.In the process of knnJ query,the knn expanded bounding box is introduced to limit the knn query range and partition data,and then the generated R-tree is used to execute knnJ query in parallel fashion,achieving high performance.This paper analyzes the communication and computation cost in theory.Experimental results and analysis in large real spatial data demonstrate that the algorithm can efficiently resolve the large scale knnJ spatial query in MapReduce environment,and has a good practical application.

关 键 词：云计算 MAPREDUCE k-近邻连接 空间查询 R-树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]