论文部分内容阅读
近年来,随着基于位置的服务(LBS)和移动互联网的快速发展,地理空间数据的数据量正在迅猛的增长。这些迅速增加的空间数据给传统的空间数据索引机制带来了新的问题,而这些传统的索引方法往往是基于内存的或者需要优化的磁盘访问的先决条件。因此,如何实现高效的空间索引和查询处理大规模空间数据成为云计算环境应用的新的需求和挑战。一种可扩展的、分布式的空间数据索引技术不失为进行高效空间数据的查询和分析的最佳选择。现在已经有几种将空间分布式索引和查询处理技术与MapReduce相结合的方法,例如R-树和基于泰森多边形的空间索引。然而,R-树不适合进行平行化,基于泰森多边形索引的查询需要额外的查询点定位和局部索引重建计算。本文对空间数据索引和查询方法存在的问题进行了研究,提出了一种改进的方法。本文首次尝试设计了一种云环境下的倒排网格索引和在该索引基础上进行的基于MapReduce的空间kNN查询。本文所做的主要工作如下:(1)针对二维空间中的数据点,本文设计了一种分布式的倒排网格索引方法,该索引方法完全符合空间数据索引的标准一动态性和简单性。由于倒排网格索引具有松耦合和无共享的特殊结构,所以该索引比较适合基于MapReduce的大规模空问数据的并行查询。(2)本文提出了一种基于MapReduce的空间倒排网格索引的建立方法和在该索引基础上的并行kNN查询算法MRCircleTrip。另外,本文还给出了算法在收敛性上的数学证明,以证明算法循环停止条件的准确性。(3)为了验证本文所设计的索引结构的可扩展性和kNN查询算法的性能,本文在建立倒排网格索引和kNN空间查询方面做了大量的实验。实验结果表明,本文所提出的索引的建立时间明显低于建立R-树和泰森多边形索引的时间,同时在可扩展性上该索引也优于其他两种索引;本文所提出的并行kNN算法在处理空间查询时至少比基于泰森多边形索引的算法快三倍。