基于R-树索引的Map-Reduce空间连接聚集操作

空间连接聚集是一种常用并且非常耗时的空间数据库操作,特别是在面对大规模空间数据集时,单机运行环境难以满足其对时空开销的需求,如何设计高效的面向云计算环境中的分布式空间连接聚集算法越来越受到人们关注。Map-Reduce作为云计算的核心模式受限于其扁平化的串行扫描操作模型,常被用来加速非索引的空间连接操作,现有工作尚无将Map-Reduce和R-树索引结合来处理空间连接聚集。因此,提出了基于R-树索引的Map-Reduce空间连接聚集算法(RSJA-MR)来更高效地返回连接聚集结果。提出一种分布式R-树索引结构以支持大规模空间数据的索引,RSJA-MR算法利用分布式R-树生成任务集,任务集的执行满足无依赖并行计算模式,很容易在Map-Reduce框架中进行表达。文中提出一种实时缓存策略以支持索引并发访问。实验结果表明:相比非索引的Map-Reduce连接聚集算法,在空间交叠连接聚集查询上,时间性能最少提升8%,在空间包含连接聚集查询上,时间性能最少提升近35%。

Processing spatial join aggregate in Map-Reduce based on R-tree

Spatial join aggregate (SJA) is a commonly used but time-consuming operation in spatial database especially facing the deluge of spatial data,SJA is difficult to be implemented on a single machine, how to design efficient distributed SJA algorithms is receiving more and more attention. Constrained by sequential scan operation assumption, Map-Reduce is usually used to accelerate the non-indexed spatial join query, none of the previous work can process SJA with both Map-Reduce and R-tree spatial index. This paper proposes a novel algorithm; R-tree based Spatial Join Aggregate with Map-Reduce (RSJA-MR), which is able to return results more efficiently. A distributed R-tree index structure is presented to index the large-scale spatial data. RSJA-MR first makes used of distributed R-tree to generate the tasks. Those tasks meet independent parallel computation and can be easy to be expressed in Map-Reduce. An index cache mechanism is provided to support the concurrent access of R-tree index. The experiment results show that compared to 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.