iGIS 时空大数据智能服务平台：AI赋能并行地理算法实践

近年来并行计算已经被广泛应用于地理空间大数据分析中，使用的并行模式大体可以分为两类，任务并行与数据并行。两种并行模式的原则都是将一个完整的大问题分解成一些子问题或子任务，调度到多个处理器上并行执行，这种问题分解、调度的模式在保证负载均衡的前提下，能够大幅度地提升计算效率。但目前高性能地理计算领域中的并行策略通常难以实现负载均衡，或仅面向某些特定应用来均衡子任务间的负载，始终缺乏一种通用的面向负载均衡的问题分解方法。

iGIS作为新一代时空大数据平台，其iGIS-AI模块采用基于AI技术优化现有空间域分解策略，负载均衡指数提升一个量级，再结合自主研发的大禹分布式任务调度系统，可大大提高计算效率。例如省级土地变更调查分析，地类图斑数量为千万级别，且分析种类多、内容复杂，分析效率低，以流量分析为例，同等条件下采用传统GIS软件结合Excel表的方式执行一次全省数据耗时约一周；基于大禹任务调度系统，采用传统并行策略算法耗时约48小时，采用AI并行策略算法耗时约32小时。

本文以并行化点云生成DEM与并行化矢量空间相交为例来介绍基于人工智能的地理空间域计算强度评估在并行地理计算中的算法实践。

并行化点云生成DEM

基于点云生成DEM通常利用插值方法，根据网格一定邻域半径内的点来内插DEM网格，其中每个DEM网格可以理解为一个栅格像素。目前已有不少插值方法用于生成DEM，包括反距离加权内插（inverse distance weighted, IDW）, 自然邻居，不规则三角网和通用克里金插值方法。选用了IDW方法来生成DEM，IDW通过平均所需点附近采样点的加权值来求解待内插值。经过分析，可选取六个候选特征包括划分单元内DEM网格数量、划分单元内采样点数量、邻域划分单元内DEM网格数量、邻域划分单元内采样点数量、划分单元内点密度以及划分单元内点分布方差（公式1）。

将候选特征输入上述所提出的计算强度评估方法，便可以生成一个计算强度预测模型。在此基础上，采用递归四叉树空间域划分方法，对本案例进行并行化改造，具体流程如图1所示。

图1. 点云内插DEM并行化过程

我们对比了提出方法与传统基于网格分解方法和传统递归四叉树分解方法。传统基于网格分解方法将空间域分解为同提出方法相同数量的划分单元，每个划分单元面积相同，并采用范围分区方法组合划分单元；传统递归四叉树分解方法同提出方法基本相同，唯一不同点在于传统方法基于经验公式评估计算强度。图2展示了三种方法在各进程的执行时间，可以看出提出方法相比于其他两种方法实现了更佳的负载均衡效果。图3对比了提出方法与两种传统方法在4、8、12、16、24个进程下的加速比以及并行效率，可以看出提出方法具有更佳性能。

图2. 提出方法与两种传统方法16和24个进程下执行时间与负载均衡比较

图3. 不同进程数下三种方法的加速比与并行效率对比

并行化矢量空间相交

空间相交是GIS中典型的空间分析功能之一，当对数以百万计的多边形对象求交时，往往耗时较长，需要并行计算提升求解效率。目前已有不少关于并行空间相交的研究，其中比较经典的方法为Partition Based Spatial-Merge Join (PBSM)，该方法采用传统的空间网格划分策略来提升并行性能，方法将空间相交划分为两个阶段，过滤和精解阶段。过滤阶段将与网格相交的多边形划分到对应网格内，精解阶段只需对每个网格内的多边形求交即可。本文在此方法上融入地理空间域计算强度预测模型。经过对该案例进行分析，本文总共得出8个候选特征，包括网格内两图层各自多边形的数量、网格内两图层各自多边形顶点数量、网格内两图层各自多边形分布方差、网格内两图层多边形均值中心点距离以及网格内参考点数量。将候选特征输入上述所提出的计算强度评估方法，便可以生成一个计算强度预测模型。本文将预测模型融入PBSM方法中对其进行优化，具体流程如图4所示。

图4. 矢量空间相交并行化过程

我们对比了提出方法与传统PBSM方法和特征辅助的PBSM（fPBSM）方法。传统PBSM方法基于规则网格分解方法划分空间域，假设每个网格具有相同的计算强度，按数量将网格均分为子域。fPBSM则使用特征作为评估计算强度的直接指标，因为目前尚未有研究推导出该案例计算强度评估公式，因此采用了网格中多边形数量来评估网格的计算强度。图5给出了三种方法在三组数据下20和24个进程的执行时间情况，观察得出提出方法在三组数据下的执行时间比较均衡，实现了较好的负载均衡性能。在三组数据上，进一步对比了提出方法与两种传统方法在4、8、12、16、20、24个进程下的加速比以及并行效率（图6）。可以看出，提出方法在三组数据以及任意进程数下，都实现了更佳的性能。

图5. 三种方法在三组数据下20和24个进程的执行时间

图6 三种方法在三组数据下不同进程数对应的加速比和并行效率

AI机器学习建模技术目前已被广泛应用于各行各业，其以黑盒的形式面向不同领域的应用者，摆脱人工建模与经验公式的束缚，自动化地完成高精度建模。本文通过并行化点云生成DEM与并行化矢量空间相交为例来介绍AI优化GIS计算的可靠性与高效性。iGIS-AI模块现已实现多种并行GIS算法的AI优化，显著的提高了并行计算效率，是产品的一大技术亮点。

作者：武汉大学-南方数码时空大数据研究中心

iGIS介绍

iGIS（Intelligent GIS，时空大数据智能服务平台），由武汉大学-南方数码时空大数据研究中心研发，以南方数码十余年技术积累与武汉大学的科研底蕴为基础，集时空大数据与地理信息人工智能技术于一体，致力于解决海量时空数据存储及高性能计算瓶颈问题，为人工智能提供数据、算法、算力支持，聚焦自然资源行业，推出一套完整的时空大数据与人工智能解决方案，并在众多项目实施中给予重大支撑，为自然资源信息化赋能。

—— 往期阅读 ——