一种基于网格索引的空间连接查询处理优化算法  

A Spatial Join Query Optimization Algorithm Based on Grid Index

作　　者：乔百友[1,2] 邓增安 王秋杰[2] 朱红印 孔德福[2] 王国仁[1,2] 

机构地区：[1]国家海洋信息中心,天津300171 [2]东北大学信息科学与工程学院,沈阳110819

出　　处：《小型微型计算机系统》2014年第10期2243-2248,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61073063;61173029;61272182;61173030)资助;国家海洋公益性项目(201105033)资助;数字海洋国家重点实验室开放基金项目(KLDO201306)资助

摘　　要：针对云环境下的空间数据连接查询处理问题,提出一种基于MapReduce框架的高效空间连接查询处理优化算法.该算法采用网格划分方法将数据空间划分成大小相同的网格单元,并将其中一类数据集中的每个空间对象,按照其中心点的位置划分到所在的网格单元中,从而避免了连接对象的复制,网格单元之间根据其所包含数据对象的交叠关系构建网格索引;对另一类数据集中的对象,仅将其复制到与网格单元中数据有交叠的网格单元,从而过滤掉不可能有连接结果的数据对象,大大减少了后续的连接计算代价.合成数据和真实数据集上的大量实验表明,本文提出的空间数据连接查询处理优化算法在性能上明显优于原有SJMR查询处理算法.Arming at the problem of spatial join query processing in cloud computing, an effective spatial join query processing optimization algorithm is proposed in this paper,which is based on the MapReduce framework. Data space is partitioned into many grid cells by using grid division approach, and each spatial object in one data set is distributed into a grid cell according to its central point posi- tion,this avoids the redundant duplication of the data object. According to the intersection relationship of data objects contained by these grid cells, a grid index is constructed to filter useless join objects. For another data set, we use the grid index to duplicate each data object only to the grid cells in which there exists one data object intersected with the data object, and thus filtering out the useless data objects, thereby greatly reducing the corresponding computational cost. Comparative experiments on synthetic data and real data sets show that the proposed spatial data join query processing optimization algorithm has obvious advantages and better performance than SJMR algorithm.

关 键 词：连接查询 MAPREDUCE 空间数据 网格索引 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]