论文部分内容阅读
对地观测、GIS和传感器网络等空间数据获取技术的革命性进步、存储器价格的显著下降以及人们希望从空间数据中获取知识等客观需求,催生了大数据,空间数据管理技术迎来了大数据时代。传统的并行计算和空间数据库技术在应对容量大、类型多样的空间查询处理和分析挑战时,遇到了可扩展性差、支持类型单一等困难。近年来,Map Reduce技术异军突起,通过集群上的分布式并行计算获得良好的系统性能,并以高度的可扩展性,满足不断增长的数据量的处理需求,成为大数据分析的主流技术之一。因此,结合Map Reduce技术进行大规模空间数据的高性能查询处理成为一种发展趋势。最近以来,这一方向已经引起国内外学者的注意,开展了初步研究并取得了一定的成果,但为了取得更好的查询效果并满足实际应用需求,在关键空间查询算法设计及性能优化等方面均存在进一步探索的巨大空间。本文从实际需求出发,借鉴传统的并行空间查询算法和空间数据库技术,结合Map Reduce并行计算模型的特点,从以下四个方面对大规模空间数据的高性能查询处理技术开展了研究:1.并行计算模型抽象与空间数据建模为指导Map Reduce框架下并行空间查询算法的设计,对并行计算模型和数据存储模型进行了研究。首先,利用无依赖并行和串行同步计算的形式化定义抽象了Map Reduce并行编程模型,采用分阶段方法对各个阶段的代价模型进行分析;其次,针对Map Reduce框架下空间数据的存储需求,在分析空间数据信息模型和空间数据对象-关系存储模型的基础上,设计了空间数据的key-value存储模型并进行了实现。2.空间数据索引的并行构建针对大规模空间数据R-树索引的构建需求,提出了基于Hilbert曲线和随机采样的并行空间划分函数生成方法,利用生成的空间划分函数,使得大规模空间数据的R-树索引构建符合Map Reduce无依赖并行和串行同步的计算抽象,并设计了并行处理阶段的算法,最后从负载均衡、构建效率和构建质量等方面实验验证算法的可行性和高效性;其次,针对大规模批量遥感影像瓦片金字塔索引的构建需求,基于全球瓦片金字塔模型,提出一种基于分辨率和空间范围自动匹配的瓦片金字塔索引的生成方法,详细设计了Map阶段瓦片并行生成和Reduce阶段瓦片并行合并处理方法,并提出了一种过滤优化方法,最后实验验证了算法的高效性和可扩展性。3.空间数据的并行连接聚集查询在面向大规模空间数据的空间连接查询上,用户经常需要连接查询中的统计聚集信息。对此,提出了Map Reduce框架下两种不同条件下的并行连接聚集算法。首先,针对非索引条件下的并行空间连接聚集问题,提出了一种Map Reduce框架下的过滤合并(Map-Reduce-Filter-Merge,MRFM)方法,Map阶段利用空间网格将整个空间连接聚集任务划分为无关联的任务子集,Reduce阶段则对每个任务执行部分聚集的空间连接聚集操作,Filter阶段对单次分配空间对象的连接聚集结果进行过滤操作,然后Merge阶段对多次分配空间对象的连接聚集结果进行合并。其次,将R-树索引引入到空间连接聚集操作中,利用分布式R-树来索引大规模空间数据并生成任务集,然后利用任务连通图进行任务划分,使其符合无依赖并行计算模型,并设计了Map和Reduce阶段的并行处理算法,比非索引的空间连接聚集操作更加自然,并且性能得到提升。4.空间数据的并行k近邻连接查询Map Reduce框架下处理k近邻连接查询的核心在于数据的划分,现有方法主要采用数据块的划分方法,但执行时间随数据规模的增长呈平方项增长,导致查询效率不高。基于分布式R-树索引,提出一种Map Reduce框架下,面向大规模空间数据集的k-近邻连接查询算法,通过引入k-近邻扩展框来进行数据划分,限定k-近邻查询范围,以提高查询效率,并且利用R-树索引简化了k近邻连接查询处理。从理论上分析了提出算法的通信和计算代价。实验结果与分析表明,提出算法在真实数据集的查询上具有良好的效率和可扩展性,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好实用价值。