一种基于网格划分的并行空间划分方法及其系统

技术领域

本发明涉及并行空间数据分析处理领域，具体说的是一种基于网格划分的并行空间划分方法及其系统。

背景技术

如今主流的GIS地理信息系统仍以串行计算为基础框架，难以充分利用和发挥当前新型硬件构架计算机资源的能力，难以满足实际应用的规模与高效需求。并行化成为当今提高地理计算效率的重要方式。对基于矢量数据的并行化地理数据计算，难点多体现在空间划分、任务调度、并行性分析等方面。空间任务分配是并行空间查询(并行范围查询、并行连接查询等)的基础，可分为空间划分(space declustering)和数据划分(data partition)两种方案。

空间划分主要是通过将空间范围划分成空间对象数量相等或者大致相等的分片集合，然后分配给不同的处理器进行本地化连接操作。针对基于拓扑关系的空间分析应用中，在分片时需要对处于边界的对象进行特殊处理，即边界对象处理问题(Boundary Object Handling)，当前有四种处理方案解决边界对象：1、副本拷贝:该方案将与空间对象相交的所有分片都保存完整的副本，在并行处理完成时，再消除并行连接过程中产生的重复结果；2、空间对象片段代理:该方案将与多分片相交的空间对象分配到某个特定分片上，并将空间对象在其余分片上的相交部分的MBR及该空间对象的指针OID(对象编号)分配给其余相交分片，该方案同样必须进行重复结果消除工作；3、副本避免：一种称为参考点方法的方案，来自不同空间关系R和S的每一对空间对象Tr和Ts，如果均被复制到多个分片中，那么Tr和Ts的空间关系判断只在二者均有副本的分片中进行。该方法计算Tr和Ts的MBR的特定参考点(对象相交角点)，并只在参考点所在的分片中进行连接计算，以避免副本。参考分片法是参考点方法的改进,该类算法必须将与多分片相交的空间对象进行复制备份；4、空间对象分割：直接将与多分片相交的空间对象沿着空间分片的边界进行分割，并将得到的空间对象片段的几何对象信息保存在索引中，在连接运算中，对各片段分别运算。该方案在分片数量很多的情况下索引结构增长，将导致大量的I/O,并且对空间对象进行分割的过程也需要额外的几何运算。

上述现有技术能够解决边界对象问题的空间划分方案中，前两种在划分阶段和结果集中都有冗余副本；第三种虽然避免了结果集中的副本，但是必须将边界对象分别拷贝到各个分区；第四种方案还需要对对象进行划分，增加了额外的分割运算过程和存储空间，当边界对象随着空间划分的进行而增多时，其额外的分割和存储消耗不可忽视。

专利公开号CN 101515284A的中国专利公开了一种基于离散网格的并行空间拓扑分析方法，具体公开了先加载数据，在由Root进程对空间对象进行数据划分，将划分后的子数据传送给多个Sub进行空间拓扑分析的技术方案。该方案中，还是需要对对象进行划分，还是存在需要额外增加分割运算和存储空间的问题，并不能很好的解决边界对象问题。

发明内容

本发明所要解决的技术问题是：提供一种基于网格划分的并行空间划分方法及其系统，有效解决空间划分时的边界对象处理过程需要额外增加数据处理量和额外占用存储空间，从而影响并行数据分析效率的问题。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于网格划分的并行空间划分方法，包括：

依据四叉树对空间对象所在的空间进行网格划分；

依据划分规则对网格进行编号；

对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR。

本发明提供的另一个技术方案为：

一种基于网格划分的并行空间划分系统，包括：

网格划分模块，用于依据四叉树对空间对象所在的空间进行网格划分；

网格编号模块，用于依据划分规则对网格进行编号；

第二构建模块，用于对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR。

本发明的有益效果在于：区别于现有技术的并行空间处理方案中会存在边界对象处理问题，从而带来额外分割运算和存储的消耗。本发明依据四叉树模型对空间进行网格划分，以及四叉树编码；确定能够包含每个空间对象的最小外包矩形的四叉树网格，构建以该四叉树网格编号为主键的空间分片索引；由于每个空间对象都包含在一个对应的四叉树网格中，因此，基于空间分片索引的空间并行运算过程，便不会出现边界对象问题的发生；相较于现有技术，显著提高并行分析处理效率，同时缩减数据存储空间。

附图说明

图1为本发明一种基于网格划分的并行空间划分方法的流程示意图；

图2为本发明实施例一的方法流程示意图；

图3(a)为本发明实施例一中基于四叉树模型的空间划分及编码规则示意图；

图3(b)为本发明实施例一中基于四叉树模型的空间划分及编码规则中第一层级划分后生成一级网格的示意图；

图3(c)为本发明实施例一中基于四叉树模型的空间划分及编码规则中第二层级划分后生成二级网格示意图；

图4为发明一种基于网格划分的并行空间划分系统的结构组成示意图；

图5为实施例三的系统结构示意图。

标号说明：

1、网格划分模块；2、网格编号模块；3、第一构建模块；

4、第二构建模块；5、获取模块；6、第三构建模块；

7、统计模块；8、分配模块；9、处理模块；10、计算模块；

11、一级划分编号单元；12、二级划分编号单元；13、划分编号单元；

21、第一选取单元；22、第二选取单元。

具体实施方式

为详细说明本发明的技术内容、所实现目的及效果，以下结合实施方式并配合附图予以说明。

本发明最关键的构思在于：依据四叉树进行空间网格划分和网格编号，基于能够包含空间对象最小外包矩形的网格，构建以网格编号为主键的空间分片索引，使每个空间对象都包含在一个对应的四叉树网格中，从而消除边界对象处理问题。

本发明涉及的技术术语解释：

请参照图1至图2，本发明提供一种基于网格划分的并行空间划分方法，包括：

依据四叉树对空间对象所在的空间进行网格划分；

依据划分规则对网格进行编号；

对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR。

从上述描述可知，本发明的有益效果在于：使用四叉树模型对空间范围进行划分，得到空间分片(网格)，并对空间分片进行四叉树编码，划分过程中，对每个空间对象，寻找能包含该空间对象最小外包矩形的四叉树格网，构建以格网编码为主键的空间分片索引，该划分方法中，每个空间对象都包含在一个对应的四叉树格网中，避免了边界对象问题的产生。

进一步的，所述依据划分规则对网格进行编号之后，进一步包括：

对应所述空间构建坐标系；

依据四叉树，计算各个网格对应的坐标。

由上述可知，获取各个网格对应的坐标，作为后续并行处理中所述网格在空间中位置的标示。

进一步的，还包括：

获取对应网格的空间对象集合；

依据所述空间对象集合构建任务候选集；

统计所述任务候选集对应的工作量；

依据工作量分配相应的任务至处理器；

所述处理器依据任务对应的空间对象的空间分片索引进行并行处理。

由上述描述可知，空间网格划分产生的分片(网格)是生成并行空间查询任务候选集的基础，本发明直接利用对应网格的空间对象集合生成任务候选集，然后统计任务候选集的工作量，再依据处理器的性能分配相应工作量的任务至对应处理器进行并行处理。相较现有技术，所生成的任务候选集中不存在冗余副本以及重叠，因此，本发明在负载均衡的提前下，显著减少并行处理的工作量，实现高效并行分析处理。

进一步的，所述依据四叉树对空间对象所在的空间进行网格划分；依据划分规则对网格进行编号具体为：

依据四叉树对空间对象所在的空间进行四等分，获取四个一级网格，并分别对一级网格进行编号；

对一级网格进行四等分，获取四个二级网格，并依据对应的一级网格的编号对二级网格进行编号；

依据预设的网格划分次数继续对所述二级网格进行相应次数的划分并编号。

由上述描述可知，本发明基于四叉树进行网格的划分和网格的编码，在前一次网格划分结果上对每个网格继续进行网格划分，新划分的网格的编码是在前一次划分的网格的编号后添加新的区域编号，从而建立区域关联，标示空间信息。

进一步的，所述对应所述空间构建坐标系；依据四叉树，计算各个网格对应的坐标具体为：

选取所述空间的一边角作为坐标原点，构建坐标系；

选取所述网格的一边角在所述坐标系的坐标作为所述网格的坐标，依据四叉树网格编码规则，计算获取所述坐标。

由上述描述可知，构建对应空间的坐标系，获取对应网格的坐标，通过对空间对象的空间分片索引中的网格编号进行分析，便可推算出该空间对象在空间中所处的位置。

请参阅图4，本发明提供的另一个技术方案为：

一种基于网格划分的并行空间划分系统，包括：

网格划分模块1，用于依据四叉树对空间对象所在的空间进行网格划分；

网格编号模块2，用于依据划分规则对网格进行编号；

第二构建模块4，用于对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR。

进一步的，还包括：

第一构建模块3，用于对应所述空间构建坐标系；

计算模块10，用于依据四叉树，计算各个网格对应的坐标。

请参阅图5，进一步的，还包括：

获取模块5，用于获取对应网格的空间对象集合；

第三构建模块6，用于依据所述空间对象集合构建任务候选集；

统计模块7，用于统计所述任务候选集对应的工作量；

分配模块8，用于依据工作量分配相应的任务至处理器；

处理模块9，用于所述处理器依据任务对应的空间对象的空间分片索引进行并行处理。

进一步的，所述网格划分模块1具体包括：

一级划分编号单元11，用于依据四叉树对空间对象所在的空间进行四等分，获取四个一级网格，并分别对一级网格进行编号；

二级划分编号单元12，用于对一级网格进行四等分，获取四个二级网格，并依据对应的一级网格的编号对二级网格进行编号；

划分编号单元13，用于依据预设的网格划分次数继续对所述二级网格进行相应次数的划分并编号。

进一步的，所述第一构建模块3具体包括：

第一选取单元21，用于选取所述空间的一边角作为坐标原点，构建坐标系；

第二选取单元22，用于选取所述网格的一边角对应所述坐标系的坐标作为所述网格的坐标，依据四叉树网格编码规则，计算获取所述坐标。

请参照图2、图3(a)至图3(c)，本发明的实施例一为：

提供一种基于网格划分的并行空间划分方法，用于并行空间任务分配的分析处理过程，有效解决现有技术的空间分片会产生边界对象处理问题，导致额外分割运算和存储的消耗。

首先，依据四叉树对空间对象所在的空间进行网格划分，并依据网格划分规则，即四叉树模型对网格进行编号；具体的网格划分和编号方式如下：

1、将空间进行并行分层处理，分为0-N层，空间数据集所在的空间范围作为第0层，不进行划分，第一层如图3(a)所示；

2、对第一层的空间进行四等分划分，获取四个一级网格，然后按上下左右(即上左、上右、下左、下右)的顺序分别给划分的一级网格区域编号A、B、C、D，将其作为第一层的网格划分结果，如图3(b)所示；

3、在第一层的四个一级网格区域上对每一个一级网格区域再继续做四等分划分，一个一级网格划分得到四个二级网格；新划分网格区域的编号是在被切割网格区域(一级网格区域)的编号后添加新的网格区域编号{A，B，C，D}其中之一获得，结果为AA，AB，AC，AD，BA，BB，BC，BD，CA，CB，CC，CD，DA，DB，DC，DD 16个区域，并作为第二层的划分结果，如图3(c)所示；

4、依据预设的网格划分次数在第二层的划分结果(二级网格)上继续进行四等分和编号，直到达到预设的划分次数；所述网格划分次数可以依据空间对象的空间大小，或者处理器的处理能力，或者并行分析处理的精度来设定。

其次，对应所述空间构建坐标系，获取对应网格的行列号，即坐标；该步骤可以在网格划分完毕后进行，也可以与网格划分过程同步进行；具体过程可以包括：

1、选取所述空间的一边角作为坐标原点，构建坐标系；优选的，可以选取空间左下角作为笛卡尔坐标系的原点；同时也将网格的左下角位置作为该网格的坐标；

2、选取所述网格的一边角对应所述坐标系的坐标作为所述网格的坐标；那么，一级网格A、B、C、D四个区域对应的坐标为(1,0)，(1,1)，(0,0)和(0,1)，二级网格A下的二级网格AA、AB、AC和AD的坐标为(3,0)，(3,1)，(2,0)和(2,1)；一级网格C为坐标原点，坐标为(0,0)。

可选的，对应网格的坐标只是为了标示网格在空间所处位置，因此，坐标系原点的选取，以及选取网格哪一点的坐标作为网格的坐标都是可以依据需求灵活的设定的，比如，还可以选取网格的中心点位置的坐标作为网格的坐标。

进一步的，同时，网格坐标的获取可以通过建立坐标系后，依据四叉树划分编码规则，计算获取对应网格的坐标。具体的，能够直接依据公式：

$>Row=\underset{k=0}{\overset{n-1}{\Sigma }}{2}^k\times r_k$>

$>Col=\underset{k=0}{\overset{n-1}{\Sigma }}{2}^k\times c_k$>

其中，Row为行号，Col为列号，n为层号；r_k是行判断函数，当将网格编号翻转后的第k+1个字母(k从0开始)是A或B的时候，r_k＝1否则r_k＝0；c_k是列判断函数，当将网格编号翻转后的第k+1个字母是B或D的时候，c_k＝1否则c_k＝0。

编码计算行列号运算实例：一空间对象P的网格编号为BCD；翻转后是DCB，经过上面的公式可以计算出它的行列号为：

Row＝2⁰×0+2¹×0+2²×1＝0+0+4＝4

Col＝2⁰×1+2¹×0+2²×1＝1+0+4＝5

可知，该空间对象的坐标为P(4,5)。

然后，对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR。

具体的，以R为例，对R中每一个空间对象R1、R2和R3构建对应的空间分片索引：

1、计算R1最小外包矩形MBR(R1)、R2最小外包矩形MBR(R2)以及R3最小外包矩形MBR(R3)；

2、分别寻找更好能够完全覆盖所述MBR(R1)、MBR(R2)以及MBR(R3)的最低层级的四叉树网格；如图3(c)所示，能够完全覆盖所述MBR(R1)的网格刚好为处于第一层级的一级网格A，MBR(R2)对应第二层级的二级网格CB；而MBR(R3)由于部分超出了网格CC，因此对应的是第一层级的一级网格C；

3、获取空间对象R1、R2和R3预设的指针OID，即ID编号，所述ID编号指向数据库中对应空间对象记录的具体数据；

4、构建由能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR组成的空间分片索引；如空间对象R1的空间分片索引项为<A,R1_id,MBR(R1)>，空间对象R2何R3的索引项分别为<CB,R2_id,MBR(R2)>和<C,R3_id,MBR(R3)>。通过空间对象所处四叉树格网的编号可以推算出该网格所在的层级号及行列号，进而可以算出该网格在空间的范围，反之亦然。

通过上述，已经对应每个空间对象都构建了空间分片索引，利用四叉树编码中隐含的空间拓扑关系，能够依据空间拓扑关系判断转换成字符串编码匹配运算，从而显著提高空间并行分析处理的效率；由于网格划分过程中，每个空间对象都包含在一个对应的四叉树网格中。因此，便不存在边界对象处理问题，从而明显减少并行分析处理的工作量，以及冗余、重叠副本而带来的额外存储空间。

本发明的实施例二为：

本实施例在实施例一的基础上进一步的延伸，相同之处不再复述，区别之处在于增加了基于空间对象的空间分片索引的负载均衡分配方案：

1、获取对应网格的空间对象集合；遍历空间内的网格，获取由网格所包含的空间对象构成的集合。特别说明的是，并非每个网格都有对应的空间对象集合；

2、依据所述空间对象集合构建任务候选集；空间任务分配的基础是任务候选集，一个任务候选可以对应一个以上的空间对象；

3、统计所述任务候选集对应的工作量；

4、依据工作量分配相应的任务至处理器；根据一定的负载均衡次数，进行并行任务的分配。优选的，可以依据所配置的处理器的性能，如双核处理器、4核处理器或者6核处理器来均分所要处理的任务；平均分配等量工作量的任务进行处理，实现多核并行处理空间任务。

5、所述处理器依据任务对应的空间对象的空间分片索引进行并行处理。

通过上述，能够实现基于空间分片索引的并行分析处理，不仅克服了边界对象处理问题，而且实现了均衡负载，实现高效地并行处理空间任务。

实施例三

请参阅图5，本实施例为对应实施例一和二的并行空间划分方法而提供的一种基于网格划分的并行空间划分系统，具体包括：

网格划分模块1，用于依据四叉树对空间对象所在的空间进行网格划分；

网格编号模块2，用于依据网格划分规则对网格进行编号；

所述网格划分模块1和网格编号模块2可以集成由一个功能模块实现，该模块具体包括：

一级划分编号单元11，用于依据四叉树模型对空间对象所在的空间进行四等分，获取四个一级网格，并分别对一级网格进行编号；

二级划分编号单元12，用于对一级网格进行四等分，获取四个二级网格，并依据对应的一级网格的编号对二级网格进行编号；

划分编号单元13，用于按照预设的网格划分次数对所述二级网格进行相应次数的划分和编号。

第一构建模块3，用于对应所述空间构建坐标系，获取对应网格的坐标；具体的，所述第一构建模块3具体包括：

第一选取单元21，用于选取所述空间的一边角作为坐标原点，构建坐标系；

第二选取单元22，用于选取所述网格的一边角对应所述坐标系的坐标作为所述网格的坐标。

第二构建模块4，用于对所述空间内每一个空间对象构建空间分片索引，所述空间分片索引包括能完全覆盖空间对象的最小网格的编号、空间对象的编号以及空间对象的最小外包矩形MBR；

进一步的，还包括：

获取模块5，用于获取对应网格的空间对象集合；

第三构建模块6，用于依据所述空间对象集合构建任务候选集；

统计模块7，用于统计所述任务候选集对应的工作量；

分配模块8，用于依据工作量分配相应的任务至处理器；

处理模块9，用于所述处理器依据任务对应的空间对象的空间分片索引进行并行处理。

综上所述，本发明提供的一种基于网格划分的并行空间划分方法及其系统，能够有效解决空间划分时产生的边界对象处理过程需要额外增加数据处理量和占用存储空间，从而影响并行数据分析效率的问题。通过依据四叉树对空间进行网格划分和编码；基于能够包含空间对象最小外包矩形的网格，构建以网格编号为主键的空间分片索引，使每个空间对象都包含在一个对应的四叉树网格中，从而消除边界对象处理问题；不仅显著提高并行分析处理效率，同时缩减数据存储空间；进一步的，基于空间分片索引而构建任务候选集，依据其对应的工作量进行并行任务分配，实现了负载均衡，从而提高空间任务查询效率。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等同变换，或直接或间接运用在相关的技术领域，均同理包括在本发明的专利保护范围内。