论文部分内容阅读
经过近半个世纪的发展,GIS在空间数据管理、空间分析方法、数据可视化三个主要方面均取得长足的进步。经典的叠加分析、缓冲区分析、网络分析等空间分析算法已经得到深入研究,尤其是频繁使用的叠加分析算法在串行执行情况下的优化基本达到理论值的极限,为满足地理信息应用领域对海量空间数据高效处理的需求,有必要对高性能计算技术在典型地理空间数据分析应用做系统研究。本文以经典叠加分析理论与技术路线为基础,结合最新并行计算体系架构,从并行空间数据域分解,空间索引快速过滤机制,并行空间运算、数据管理等多个层面深入分析和研究并行化叠加分析算法基础理论和关键技术问题。本文研究工作主要内容如下: 1)在研究国内外相关文献和技术的基础上,分析利用并行计算模式进行叠加分析算法研究的必要性和可行性。在GIS软件开发设计中,从算法并行化和充分利用现有计算机硬件的并行架构体系(多核架构、高性能集群计算)两方面提高系统处理分析空间数据的能力,为高性能地学计算中的集群GIS、云计算GIS提供底层的并行加速基础。确定主要以数据分治为主线的并行化方法。 2)在进行并行化叠加分析操作之前,研究地理空间数据的预处理方法,探索使用并行空间数据索引、多策略Hilbert空间填充曲线排序分解、k-means空间聚类等机制对空间数据进行解簇,为叠加分析中的数据分发处理提供支持。空间数据分解着重探讨地理要素在空间域中的空间关联关系,在并行分解中将地理距离相近的数据分配到同一节点计算,尽量保持叠加算法执行程序和叠加数据的本地化。 3)以典型的合并和求交操作为例,探索叠加分析算法的并行化原理与方法。算法并行化研究从多种粒度的空间数据组织方式入手,在点、线段、几何对象、图层粒度层次上尝试计算过程的并行化。其中细粒度的算法如点面叠加以多核方式并行化,对象与图层的叠加以MPI粗粒度的方式进行。在Hilbert空间排序分解的基础上,使用MPI并行工具实现相邻多边形的叠加合并操作;实现二叉树形式的并行多边形合并。利用主从式并行索引分解实现线面的并行裁剪。编程实现并行算法并组织实验,证明算法的正确性和加速性能。 4)根据空间拓扑关系对叠加分析后的图层进行一致性维护和检查,实现悬线检查、重叠线检查等功能。最后基于以上并行算法设计理论分析和空间数据分解策略,实现分布式并行空间分析系统框架,研发实现读写分离的MySQL空间数据库集群,在其基础上探索并行叠加分析中的I/O控制。