基于空间填充曲线排列码划分的并行缓冲区算法

缓冲区计算是地理信息系统空间分析的基本功能之一。在矢量缓冲区研究方面,以往大多聚焦缓冲区生成算法,这些优化方法在单机计算环境中针对大规模空间数量数据的计算效率提升是有限的,因而需要并行环境下的改进方法来进一步破解计算瓶颈。本文基于Map Reduce计算模型和分布式内存计算框架,提出了一种基于空间填充曲线排列码划分的并行缓冲区分析算法(SPBM),基于空间填充曲线编码进行数据排序和范围划分,对跨越网格的数据采用近似切分方法,在考虑负载均衡的前提下对任务并行分解,之后按照给定深度的"树状"方式进行结果合并。本文在单机和集群两种环境下利用实际道路网等数据进行了实验。同等环境下,相较于目前流行的GIS软件——QGIS和Post GIS计算性能提升明显,相较于现有其他并行优化方法效率提升超过50%。这样的优化分析方法对于GIS中其他矢量分析算法的并行算法也具有一定的借鉴意义。

A Parallel Vector Buffer Analysis Algorithm Based on SFC Region Partition

Buffer analysis is one of the basic functions of spatial analysis in GIS(geographic information system). In the field of vector buffer analysis, most of the researches have been concentrated on the buffer generation algorithms in the past. However, the optimization effect of those improvement in the stand-alone computing environment is limited, thus the parallel method is needy to improve the efficiency further. Based on the MapReduce calculation model and the distributed in-memory computing framework, a SFC Partition-based Buffer Method (SPBM) is proposed. Improvements were mainly produced on three aspects:partitioning the data based on spatial filling curve to retain spatial aggregation attribute, decomposing tasks while taking load balance into consideration, as well as merging the task in tree-like method with the given depth. Using the real-world road data, experiments were carrying out in both stand-alone and cluster environment. Compared with the popular GIS software—QGIS and PostGIS in the same experiment environment, the performance improved significantly. In addition, it reached more than 50% performance enhancement than some other parallel methods.