| 引用本文: | 刘义,陈荦,景宁,等.基于R-树索引的Map-Reduce空间连接聚集操作.[J].国防科技大学学报,2013,35(1):136-141.[点击复制] |
| LIU Yi,CHEN Luo,JING Ning,et al.Processing spatial join aggregate in Map-Reduce based on R-tree[J].Journal of National University of Defense Technology,2013,35(1):136-141[点击复制] |
|
| |
|
|
| 本文已被：浏览 9896次 下载 7234次 |
| 基于R-树索引的Map-Reduce空间连接聚集操作 |
| 刘义, 陈荦, 景宁, 熊伟 |
|
(国防科技大学 电子科学与工程学院，湖南 长沙 410073)
|
| 摘要: |
| 空间连接聚集是一种常用并且非常耗时的空间数据库操作，特别是在面对大规模空间数据集时，单机运行环境难以满足其对时空开销的需求,如何设计高效的面向云计算环境中的分布式空间连接聚集算法越来越受到人们关注。Map-Reduce作为云计算的核心模式受限于其扁平化的串行扫描操作模型,常被用来加速非索引的空间连接操作，现有工作尚无将Map-Reduce和R-树索引结合来处理空间连接聚集。因此，提出了基于R-树索引的Map-Reduce空间连接聚集算法(RSJA-MR)来更高效地返回连接聚集结果。提出一种分布式R-树索引结构以支持大规模空间数据的索引，RSJA-MR算法利用分布式R-树生成任务集，任务集的执行满足无依赖并行计算模式，很容易在Map-Reduce框架中进行表达。文中提出一种实时缓存策略以支持索引并发访问。实验结果表明：相比非索引的Map-Reduce连接聚集算法，在空间交叠连接聚集查询上，时间性能最少提升8%，在空间包含连接聚集查询上，时间性能最少提升近35%。 |
| 关键词: 云计算 Map-Reduce 空间连接聚集 R-树 |
| DOI： |
| 投稿日期：2012-07-09 |
| 基金项目:国家863计划项目（2011AA12A306）；国家自然科学基金资助项目（61070035） |
|
| Processing spatial join aggregate in Map-Reduce based on R-tree |
| LIU Yi, CHEN Luo, JING Ning, XIONG Wei |
|
(College of Electronic Science and Engineering, National University of Defense Technology, Changsha 410073, China)
|
| Abstract: |
| Spatial join aggregate (SJA) is a commonly used but time-consuming operation in spatial database. Especially when faced with the deluge of spatial data，SJA is difficult to be implemented on a single machine. Consequentially, how to design efficient distributed SJA algorithms is receiving more and more attention. Constrained by the sequential scan operation assumption, Map-Reduce is usually used to accelerate the non- indexed spatial join query, but none of the previous work can process SJA with both Map-Reduce and R-tree spatial index. Thus, a novel algorithm, R-tree based Spatial Join Aggregate with Map-Reduce (RSJA-MR) was proposed, which is able to return results more efficiently. A distributed R-tree index structure was presented to index the large-scale spatial data. RSJA-MR first made use of distributed R-tree to generate the tasks. Those tasks met independent parallel computation and could easily be expressed in Map-Reduce. An index cache mechanism was provided to support the concurrent access of R-tree index. The experiment results show that, compared with the non-indexed SJA , the time performance of RSJA-MR is improved at least by 8% for spatial intersection join aggregate and by 35% for spatial containment join aggregate. |
| Keywords: cloud computing Map-Reduce Spatial Join Aggregate R-tree |
|
|
|
|
|
