###
Journal of Software:2013.24(8):1836-1851

MapReduce框架下基于R-树的k-近邻连接算法
刘义,景宁,陈荦,熊伟
(国防科学技术大学 电子科学与工程学院, 湖南 长沙 410073)
Algorithm for Processing k-Nearest Join Based on R-Tree in MapReduce
LIU Yi,JING Ning,CHEN Luo,XIONG Wei
(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3680   Download 5067
Received:November 12, 2012    Revised:January 25, 2013
> 中文摘要: 针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce 框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce 并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速构建算法和基于R-树的并行k-近邻连接算法.在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce 框架下非常容易进行表达.在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用R-树索引进行k-近邻连接查询,提高了查询效率.从理论上分析了所提出算法的通信和计算代价.实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值.
中文关键词: 云计算  MapReduce  k-近邻连接  空间查询  R-树
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61070035, 41271403); 国家高技术研究发展计划(863)(2011AA120306, 2007AA120402); 高等学校博士学科点专项科研基金(20104307110017) 国家自然科学基金(61070035, 41271403); 国家高技术研究发展计划(863)(2011AA120306, 2007AA120402); 高等学校博士学科点专项科研基金(20104307110017)
Foundation items:
Reference text:

刘义,景宁,陈荦,熊伟.MapReduce框架下基于R-树的k-近邻连接算法.软件学报,2013,24(8):1836-1851

LIU Yi,JING Ning,CHEN Luo,XIONG Wei.Algorithm for Processing k-Nearest Join Based on R-Tree in MapReduce.Journal of Software,2013,24(8):1836-1851