地理信息系统中的矢量空间叠加分析并行方法及系统

摘要

本发明提供一种地理信息系统中的矢量空间叠加分析并行方法。该方法包括：根据输入图层和叠加图层的数据类型以及叠加操作类型决定图层划分策略以确定待划分图层；分离所述待划分图层的空间数据，并将所述分离的空间数据分配给不同的子任务，以并行执行相关空间数据的叠加；合并所述不同的子任务的空间数据叠加结果，以输出最终的叠加分析结果。本发明采取了灵活有效的空间数据划分策略，提高了并行子任务的计算效率以及整体叠加分析方法的负载均衡。

说明书

技术领域

本发明涉及地理信息系统，尤其涉及一种矢量空间叠加分析的并行方法及系统。

背景技术

地理信息系统(GIS，Geographic Information System)是一门结合地理学、地图学、遥感以及计算机等科学的综合性学科。GIS的主要内容包括对具有空间属性的地理数据的管理、分析和显示。其中，空间分析是由已知的地理数据通过位置计算、属性继承和统计分析等方式，产生信息量更加丰富的地理数据，为地理信息系统提供了强大的空间数据分析能力。根据空间数据类型的不同，空间分析算法可分为矢量空间分析和栅格空间分析两类，以矢量数据为分析对象的叠加分析算法是矢量空间分析算法中的重要分析方法。

如图1所示，在常见的GIS系统中，采用分层方式组织地理景观，同一区域的整个数据集表示了该地区的地理景观的内容，叠加分析是在统一空间参考系统下，将相关的主题层组成的数据层进行一系列集合运算，产生新的数据图层的过程。最基本的叠加分析是在两个图层上的操作，通常被称为输入图层和叠加图层，多图层的叠加分析可以在两个图层的叠加分析的基础上通过重复操作来实现。

目前，随着应用需求的提高，空间数据表现出结构复杂化、规模海量化和分析需求实时化的特点，同时由于计算机集群技术以及多核系统的迅速发展，人们逐渐采用并行叠加分析方法来提高提高空间分析算法效率。

然而，现有的并行叠加分析方法中，为不破坏原有串行算法的高效数据结构，通常采用基于任务级的粗粒度的并行模式，通过对输入图层进行空间数据划分来形成多个不同的区域，由各个子进程分别完成独立区域的叠加操作，然后归并得到最终叠加结果，因此，传统算法通常只针对单一的输入图层进行数据划分，而且，目前的并行叠加分析方法，例如Open MP、MPI、CUDA等，由于空间数据存在空间邻近性以及空间要素大小不一等特点，通常存在负载不均，并行效率低，在高性能集群中并行扩展性不足等问题。

发明内容

本发明的目的在于克服上述现有技术的缺陷，提供用于矢量空间叠加分析的并行化方法。

根据本发明的第一方面，提供一种地理信息系统中的矢量空间叠加分析并行方法。该方法包括：

步骤1：根据输入图层和叠加图层的数据类型以及叠加操作类型决定图层划分策略以确定待划分图层；

步骤2：分离所述待划分图层的空间数据，并将所述分离的空间数据分配给不同子任务，以并行执行相关空间数据的叠加；

步骤3：合并所述不同子任务的空间数据叠加结果，以输出最终的叠加分析结果。

优选地，所述图层划分策略包括单一图层划分策略和多图层划分策略。

优选地，所述单一图层划分策略包括：对于所述输入图层和叠加图层的点面叠加，当所述叠加操作类型是交、提取、同一时，划分所述输入图层；对于所述输入图层和叠加图层的线线叠加，当所述叠加操作类型是交时，确定划分包含空间要素多的图层；对于所述输入图层和叠加图层的线面叠加，当所述叠加操作类型是裁剪、提取、交、差时，确定划分所述输入图层；对于所述输入图层和叠加图层的面面叠加中，当所述叠加操作类型是提取、裁剪、差、对称差、同一时，确定划分所述输入图层；对于所述输入图层和叠加图层的面面叠加中，当所述叠加操作类型是交、更新时，确定划分包含空间要素多的图层。

优选地，在采用单一图层划分策略的情况下，步骤2包括：利用希尔伯特空间填充曲线分解所述划分图层的空间数据；基于空间数据的空间邻近性特征确定分解的空间数据的索引；定义任务盒，该任务盒规定了能够容纳空间要素的数据大小；按照所述空间数据索引，对任务盒进行填充，以获得多个被填充有空间要素的任务盒；为每个子任务分配固定数量的任务盒，以确定每个子任务需要处理的空间数据。

优选地，所述多图层划分策略包括：对于所述输入图层和叠加图层的面面叠加中，当所述叠加操作类型是并时，确定划分所述输入图层和叠加图层。

优选地，在采用多图层划分策略的情况下，步骤2包括：对于输入图层和叠加图层，分别采用空间填充曲线Hilbert方法分隔成多个区域并对这些区域进行空间索引；根据输入图层和叠加图层的数据规模规定任务盒的数据大小，确保两个图层具有相同的任务盒数量；按照空间填充曲线的索引，对任务盒进行填充；将任务盒均匀分配给各个子任务，以确定每个子任务需要处理的输入图层和叠加图层的空间数据。

优选地，步骤3包括：

步骤31：先完成的子任务接收后完成的子任务的空间数据叠加结果并与自身的数据叠加结果进行合并；

步骤32：合并所有子任务的数据叠加结果，以输出最终的叠加分析结果。

优选地，在步骤31和步骤32中，先完成的子任务接收后完成的子任务的空间数据叠加结果是序列化为WKB格式的二进制流；在输出最终的叠加结果之前，还包括对所有子任务的数据叠加结果执行反序列化操作。

根据本发明的第二方面，提供了一种地理信息系统中的矢量空间叠加分析并行系统。该系统包括：用于根据输入图层和叠加图层的数据类型以及叠加操作类型决定图层划分策略以确定待划分图层的装置；用于分离所述待划分图层的空间数据，并将所述分离的空间数据分配给不同的子任务，以并行执行相关空间数据的叠加的装置；用于合并所述不同的子任务的空间数据叠加结果，以输出最终的叠加分析结果的装置。

优选地，在该系统中，所述图层划分策略包括单一图层划分策略和多图层划分策略。

与现有技术相比，本发明的优点在于：根据不同的数据类型和叠加操作的类型，采用不同的空间数据划分策略，提高了并行子任务划分的灵活性和有效性；在子任务划分的过程中，考虑了空间要素邻近性特征和计算任务的负载均衡性，提高了计算效率并提升了整体叠加算法的负载均衡；对于空间数据叠加的中间结果归并通过序列化编码完成字符串拼接，进一步提高了并行计算的归并效率。

附图说明

以下附图仅对本发明作示意性的说明和解释，并不用于限定本发明的范围，其中：

图1示出了叠加分析的示意图。

图2示出了根据本发明一个实施例的矢量空间叠加分析并行方法的示意流程图。

图3示出了根据本发明一个实施例的对矢量空间数据进行外包过滤的示意图。

图4示出了根据本发明一个实施例的主进程调度的示意流程图。

图5示出了根据本发明一个实施例的子进程调度的示意流程图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现参照附图对本发明提出的矢量空间叠加分析的并行方法及系统进一步详细说明。

图2示出了根据本发明一个实施例的矢量空间叠加分析方法的示意流程图。在该实施例中，使用MPI(Message Passing Interface)消息传递机制来实现叠加分析的并行化处理过程，其遵循主从架构模式。

步骤S110，读取输入图层和叠加图层的矢量数据。

在该步骤中，读取与空间叠加相关的数据，即输入图层和叠加图层的矢量数据，并在内存中构建矢量空间数据对象。例如，首先初始化MPI进程，加载程序相关的参数，如数据库的存储地址或外存路径等；然后根据初始化进程获取的地址，读取参与叠加分析的输入图层和叠加图层的矢量数据。

步骤S120，确定数据划分策略

在该步骤中，基于输入图层和叠加图层的数据类型以及叠加分析操作类型决定数据划分策略，即确定是否进行图层划分，是进行单一图层划分或多图层划分等。

通常，矢量空间数据包括点、线、面三种基本类型上，例如，某个点可能代表一个城市，某个线可能代表一条铁路，某个面可能代表一个省区。在叠加分析计算中，并不关心这些几何要素对应哪个地理数据，而只关心它们的坐标值。

输入图层和叠加图层可以是点图层、线图层或面图层。根据输入图层和叠加图层的不同数据类型，叠加分析分为点点叠加、点线叠加、点面叠加、线线叠加、线面叠加和面面叠加等。

矢量叠加分析操作类型包括交、并、差、补、对称差、裁剪、过滤、更新、同一等。

为了将叠加分析的任务分解为不同的子计算任务，首先需要确定对图层进行划分以确定不同子任务的计算区域，也称为空间数据划分。在一个实施例中，采用表1所示来确定不同情况下的空间数据划分策略。

表1：空间数据划分策略

由表1可知，对于输入图层和叠加图层的线面叠加，当叠加操作类型是裁剪、提取、交、差时，划分线图层，确定进行单一图层划分，在此实施例中，即划分输入图层。

对于输入图层和叠加图层的面面叠加中，当操作类型是提取、裁剪、差、对称差、同一时，划分输入图层，当操作类型是交、更新时，划分包含空间要素多的图层等。例如，如果输入图层包含的空间要素较多，则划分输入图层，反之，如果叠加图层包含更多的空间要素，则划分叠加图层。

对于输入图层和叠加图层的面面叠加中，当操作类型是并时，同时划分所述输入图层和所述叠加图层，采用多图层的划分策略。

而对于表1中的其它情况，则不进行图层划分，可采用现有的串行算法来进行叠加分析。

根据本发明的数据划分策略根据不同情况分为三种类型，即：划分输入图层；划分包含空间要素多的图层，或称大图层，其可以是输入图层也可以是叠加图层；划分多图层，即输入图层和叠加图层。

其中，多图层划分是针对面、面叠加的并操作，这种操作将叠加过程中产生的结果要素全部整合在一起，因此，参与叠加分析的两个图层可以同时被分解为若干子任务；对于面、面叠加的交操作和线、线叠加的交操作，由于从几何计算角度考虑，交换输入图层和叠加图层不会对几何结果造成影响，因此可以选择更为复杂的图层，即包含空间要素更多的图层来进行数据划分。

综上所述，本发明的数据划分策略根据不同的数据类型和叠加分析的操作类型，同时考虑了输入图层和叠加图层，从而提高了空间数据划分的灵活性和有效性。

步骤S130，执行单一图层划分。

在确定采用单一图层划分策略的情况下，执行该步骤S130。在此步骤中，包括进行空间数据划分以及将划分之后的空间数据分配给子任务的过程。其中，空间要素(即点、线或面)作为空间数据划分的最小数据独立单元，而划分之后的空间要素集合作为子任务计算的基本单位。

在一个实施例中，采用空间填充曲线Hilbert来进行单一图层的数据划分。具体而言：利用Hilbert曲线将待划分的单一图层分隔成多个区域(空间数据)，对这些区域进行编码，以为每个区域指定唯一的空间索引标号，并保持各区域的空间邻近性，即相邻区域的索引标号也相邻。通过这种方式，可以将二维空间的数据降维至一维空间，同时确保了空间要素的空间邻近性特征。

进一步地，为每个子任务分配划分之后的空间数据。

在一个实施例中，采用定义任务盒的方式来分配每个子任务所处理的空间要素。具体过程包括：根据叠加分析的任务规模，定义一个固定大小的任务盒，该任务盒规定了可容纳空间要素的数据大小，或称空间要素集合；按照空间填充曲线的索引标号，对任务盒进行填充，当任务盒中空间要素的数据饱和时，转入下一个盒子填充，直到最后一个任务盒。

应注意的是，当某一个空间要素的数据大小大于任务盒时，该空间要素独自占据一个任务盒。

在本文中，定义任务盒的作用是确保每个盒子中空间要素的数据大小基本一致，而每个盒子中可能存在若干个空间要素。例如，规定每个盒子最多可以装4MB的数据，对任务盒填充之后，盒子1中存在4个空间要素，这4个要素的总数据规模是4MB，盒子2中存在1个空间要素，这个要素的数据规模也是4MB。

然后，可以将填充完的任务盒分配给各个子任务，例如，可以均匀分配或根据执行子任务的节点/进程的处理能力而为子任务分配不同数量的任务盒。通过这种方式，每个子任务会被分到若干个任务盒，处理这若干个任务盒中的空间要素。

通过空间填充曲线，可以实现二维空间数据在一维字符串上的表达，因此，这种通过定义任务盒来分配子任务的方式，可以保证子任务处理的空间要素是具备空间区域特征。此外，每个并行子任务处理的是固定数量的任务盒，因此，可以确保并行子任务的负载均衡性。本领域的技术人员应当理解，还可以采用其它的空间填充曲线来进行空间数据划分，例如，Z曲线等

为了减小叠加分析的计算范围，在进行单一图层划分之后，可以利用被划分图层的最小外包矩阵(MBR)对另外一个参与计算的图层进行外包过滤，通过这种方式，可以进一步提高子任务的计算效率。图3示出了现有技术中的矢量空间数据外包过滤操作的示意图。

步骤S140，执行多图层划分

在确定采用多图层划分策略的情况下，执行步骤S140。

例如，类似于步骤S130，执行多图层划分的过程具体包括：对于输入图层和叠加图层，分别采用空间填充曲线Hilbert方法分隔成多个区域并对这些区域进行空间索引标号；根据输入图层和叠加图层的数据规模规定任务盒的数据大小，确保两个图层具有相同的任务盒数量；按照空间填充曲线的索引标号，对任务盒进行填充并均匀分配给各个子任务。

通过这种方式，可以为每个子任务分配需要处理的输入图层和叠加图层的空间数据(或称空间要素集合)，并保证了每个子任务所处理的数据规模的均衡性，从而提高了子任务并行处理速度。

步骤S150，调度子任务。

在此本步骤中，将子任务分配给主进程或子进程来执行。

图4示出了根据本发明的一个实施例的主进程调度的示意图。主进程主要负责侦听子进程的状态、维护调度池，向子进程分配或调度子任务以及后续的子任务结果归并。例如，当主进程获取子进程的完成消息之后，将子进程的ID写入调度池，当调度池中存在两个进程ID时，主进程向该两个子进程发送结果归并指令。

在某些情况下，根据计算叠加分析任务的规模，在进程数量较多时，主进程仅作为调度进程，在进程数量较少时，主进程也可以参与部分子任务的计算，参见图4所示，计算局部解即是指主进程获取需要执行的子任务，在这种情况下，为了实现主进程和其它子进程之间的空间数据交互，需要将内存中的主进程和子进程执行的子任务的空间数据对象序列化为标准的二进制流。

步骤S160，并行执行子任务。

各个子进程获得主进程分配的计算子任务之后，分别读取需要操作的空间要素对象，并独立完成叠加分析操作，在叠加分析完成之后，向主进程发送子任务完成指令。

步骤S170：主进程归并子任务的叠加结果

具体而言，叠加结果的归并过程包括以下几方面的内容：

子任务结果数据序列化：

在并行子任务执行中，各个子进程维护独立的内存空间，为实现不同子进程之间的空间数据交互，将内存中的空间数据对象序列化为标准二进制流。例如，采用WKB(well-known binary)格式作为内存数据交换的中间格式，序列化的处理过程是：首先，在首部存储该段WKB的字节长度，占用四个字节；其次，存储空间数据的类型，占用一个字节；然后，存储空间数据的数据规模，占用四个字节；最后，依次存储各个空间对象。该序列化编码技术将WKB在被读入数据接收方子进程后，在WKB的前端追加四个字节，以记录该WKB的长度。

并行子任务归并调度：

在此实施例中，为了缓解主进程的负载压力，防止产生进程枷锁，造成负载不均，子任务的结果归并遵循先计算完成先合并的原则。如图5所示的对子进程的调度示意图，主进程/主节点可指示先完成任务的子进程作为数据接收方，后完成任务的子进程作为数据发送方，即由先完成任务的子进程接收来自于后完成任务的子进程的叠加结果数据，与自身的结果数据归并之后，传回主进程。

子任务结果归并：

子进程获取主进程发送的归并指令后，按照数据发送方或接收方的要求发送或接收指定进程的数据。数据发送子进程在完成发送任务后，经主进程消息确认注销，数据接收子进程完成归并任务后向主进程发送任务完成消息，并进入侦听状态，等待主进程进一步调度。

结果反序列化：

主进程在归并任务完成之后，统一进行WKB反序列化操作。首先，解析WKB字符串的长度标识，然后解析对应后续的WKB内容，再获取下一个WKB长度标识。按照字符串长度标识区分各个WKB段，依次完成反序列化解析，构造空间要素，生成结果图层。

步骤S180：输出最终的叠加图层。

最终的结果图层数据可以存储在空间数据库中或以文件的形式存储，数据存储格式包括shapefile，MySQ和PostGIS等。

本发明的叠加分析方法可以集成在ArcGIS、HiGIS等GIS软件平台以执行各类空间叠加分析的任务。本发明的方法可以应用于不同的并行环境，例如，单机多核和并行集群架构。

以上已经描述了本发明的各实施例，上述说明是示例性的，并非穷尽性的，并且也不限于所披露的各实施例。在不偏离所说明的各实施例的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。本文中所用术语的选择，旨在最好地解释各实施例的原理、实际应用或对市场中的技术改进，或者使本技术领域的其它普通技术人员能理解本文披露的各实施例。