论文部分内容阅读
随着对地观测技术和位置服务技术的快速发展,空间数据规模急剧增加,己成为大空间数据,如何利用云计算对这类数据进行高效的空间连接查询处理,是当前空间数据管理领域的研究热点之一。现有的基于MapReduce的空间连接查询处理算法,如PPBSM等存在过滤能力弱、数据过度复制等问题,并且计算后还需要进行重复避免,这样带来了额外的CPU和I/O代价。为此,本文针对空间连接查询存在的问题,进行了深入研究,主要做了以下几方面的工作。首先,针对现有MapReduce空间连接查询处理算法存在的过度复制等问题,提出了两种空间连接查询优化算法,即基于过滤的空间连接查询优化算法(FBSJ)和基于网格扩充的空间连接优化算法(GEBSJ)。FBSJ算法利用经过收缩的内部网格的MBR过滤掉部分无用的跨分区单元对象,降低了Reduce阶段的计算代价。GEBSJ算法采用基于R-tree的网格索引来过滤无用连接对象,并减少连接对象的多余复制。该算法利用一类数据预处理扩充原始网格并构建网格索引,另外一类数据搜索网格索引进行数据复制,这样会降低数据的复制量同时无需重复避免,分别从CPU和I/O角度优化了算法。其次,提出了一种改进的基于分布式R*树索引的空间连接查询处理算法。本文引入分布式R*树并对其进行了改进,首先按照Hilbert空间填充曲线编码使得空间区域数据实现均匀划分,并在每个分区中构建局部R*树索引,然后利用这些分布式R*树索引构建一个全局索引信息文件。在进行连接计算时,如果两类数据集都存在索引,则利用全局索引信息文件生成任务队列,然后执行基于R*树的连接查询处理；如果只有一类数据集存在索引,则充分利用该索引信息将无索引数据复制分配到各个子索引所在的Reducer任务上并行构建索引,然后再执行基于R*树的连接查询处理。由于分布式索引的存在,相对于处理无索引数据的PPBSM算法,查询性能最高能提升38.5%。最后,通过实际数据集和合成数据集上的大量实验,对本文所提出的两类空间连接查询处理算法进行了测试分析。实验结果表明,本文所提出的两种无数据索引空间连接查询优化算法的性能要明显优于PPBSM算法；而采用分布式索引的空间连接查询处理算法能够大大加快空间连接查询处理速度,具有良好的性能和适应性。