空间拓扑分析操作的并行处理技术研究

摘要

空间拓扑分析是空间数据库操作的重要组成部分，在拥有海量数据的空间数据库中，应用拓扑分析谓词的空间操作的响应时间并不能完全满足用户实时响应的要求，因此本文提出应用并行机制解决空间关系分析时间长的问题。P-STZWare是南京航空航天大学研制的基于离散网格的并行空间关系分析集，本文围绕P-STZWare的主要工作和创新点如下：
　　 ⑴根据传统数据并行处理步骤结合空间数据的特征，提出了基于离散网格的空间数据并行处理5个步骤，P-STZWare 按照这5个步骤在保证空间分析结果正确的前提下，对空间对象进行合理的数据划分，划分成空间对象子集，并通过负载均衡，使得集群中的各子进程能够并行的进行空间关系分析。
　　 ⑵根据空间数据的特点，提出了自顶向下和自底向上两种空间数据划分方法。其中，自顶向下数据划分包括空间对象正规划分和基于种子树的划分；自底向上数据划分包括平面扫描划分。P-STZWare中并行空间拓扑分析操作的数据划分结合了正规划分和平面扫描划分，保证了划分之后空间对象仍维持之间的关系不变，并保证数据分配后负载均衡。
　　 ⑶设计与实现了基于离散网格的并行空间分析集P-STZWare，将其中算法大致分为四类，并对并行空间拓扑分析算法（parallel spatial topological analysis algorithm，PSTA算法）的性能进行了分析，用并行系统的两个度量加速和效率衡量了它对相应的串行算法性能的提高，最后提出“一次划分，多次并行”策略提高P-STZWare中并行算法的效率。通过实验得出：①并行空间拓扑分析操作的处理时间并不是随处理器数目增多线性递减，而是会达到饱和；②在采用“一次划分，多次并行”策略后，子处理器并行空间拓扑分析操作对相应串行操作的性能在省去了通信代价的情况下有了线性加速。