主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘义,景宁,陈荦,熊伟.MapReduce框架下基于R-树的k-近邻连接算法.软件学报,2013,24(8):1836-1851
MapReduce框架下基于R-树的k-近邻连接算法
Algorithm for Processing k-Nearest Join Based on R-Tree in MapReduce
投稿时间:2012-11-12  修订日期:2013-01-25
DOI:10.3724/SP.J.1001.2013.04377
中文关键词:  云计算  MapReduce  k-近邻连接  空间查询  R-树
英文关键词:cloud computing  MapReduce  k-nearest neighbor join  spatial query  R-tree
基金项目:国家自然科学基金(61070035, 41271403); 国家高技术研究发展计划(863)(2011AA120306, 2007AA120402); 高等学校博士学科点专项科研基金(20104307110017)
作者单位E-mail
刘义 国防科学技术大学 电子科学与工程学院, 湖南 长沙 410073 liu.yi.nudt@gmail.com 
景宁 国防科学技术大学 电子科学与工程学院, 湖南 长沙 410073  
陈荦 国防科学技术大学 电子科学与工程学院, 湖南 长沙 410073  
熊伟 国防科学技术大学 电子科学与工程学院, 湖南 长沙 410073  
摘要点击次数: 3124
全文下载次数: 4561
中文摘要:
      针对大规模空间数据的高性能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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利