EN中文

地球信息科学学报 >

2017 , Vol. 19 >Issue 9: 1217 - 1227

DOI: https://doi.org/10.3724/SP.J.1047.2017.01217

全空间信息系统应用

全空间下并行矢量空间分析研究综述与展望

  • 邱强 , 1, * ,
  • 秦承志 2 ,
  • 朱效民 3 ,
  • 赵晓芳 1 ,
  • 方金云 1
展开
  • 1. 中国科学院计算技术研究所 计算机应用研究中心, 北京 100190
  • 2. 中国科学院地理科学与资源研究所 资源与环境信息系统国家重点实验室,北京100101
  • 3. 山东省计算中心,济南 250015

作者简介：邱 强(1987-),男,工程师,研究方向为地理信息系统并行计算及空间分析。E-mail:

收稿日期: 2017-05-12

  要求修回日期: 2017-08-11

  网络出版日期: 2017-10-09

基金资助

国家重点研发计划项目“全空间信息系统与智能设施管理”（2016YFB0502300）子课题“多粒度时空对象组织与管理”（2016YFB0502302）

收起

Overview and Prospect on Spatial Analysis of Parallel Vectors in Pan-spatial Concept

  • QIU Qiang , 1, * ,
  • QIN Chengzhi 2 ,
  • ZHU Xiaomin 3 ,
  • ZHAO Xiaofang 1 ,
  • FANG Jinyun 1
Expand
  • 1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
  • 2. State Key Laboratory of Resources and Environmental Information System, Institute of Geographic Sciences and Natural Resources Research, Chinese Academy of Sciences, Beijing 100101, China
  • 3. Computer Science Center of Shandong Province, Jinan 250015, China
*Corresponding author: QIU Qiang, E-mail:

Received date: 2017-05-12

  Request revised date: 2017-08-11

  Online published: 2017-10-09

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

新一代并行空间分析将面临空间大数据分析和实时空间分析服务的挑战。矢量空间计算作为GIS系统中的重要组成部分,在并行化算法设计中存在负载不均,并行扩展性差,IO性能低等技术瓶颈。本文首先从应用需求和技术发展的演变历史回顾了矢量空间分析算法发展过程;然后,从研究现状的角度详细阐述了并行矢量空间分析计算的研究成果,总结了并行空间分析算法的算法特征和技术瓶颈,对不同并行编程模型进行了对比,并提出了并行空间分析算法的研发流程;最后,从发展前景的角度预测了全空间信息系统中基于多粒度时空对象的空间数据模型和计算方法的发展趋势,提出了以内存计算等技术实现存算一体化的新型空间数据模型和分析方法的技术趋势。

关键词： 地理信息系统; 矢量空间分析; 并行计算; 全空间信息系统; 多粒度时空对象; 存算一体化

本文引用格式

邱强 , 秦承志 , 朱效民 , 赵晓芳 , 方金云 . 全空间下并行矢量空间分析研究综述与展望[J]. 地球信息科学学报, 2017 , 19(9) : 1217 -1227 . DOI: 10.3724/SP.J.1047.2017.01217

Abstract

The new generation of parallel spatial analysis in pan-spatial information system is challenged by analysis of spatial big data and real-time spatial service. As one of the most important part of GIS, vector spatial analysis has some performance bottlenecks such as load unbalance, less ability of parallel expansion and low I/O efficiency. First, we review the history of the developing process of vector spatial analysis from application requirement and technical progress. Then, we expound the research findings of spatial analysis of parallel vector, summarize the algorithm features and technical bottlenecks, compare the different parallel programming model and present the parallel spatial algorithm of R&D processing. Finally, we predict the spatial data model in the future and the computing method based on spatio-temporal objects of multi-granularity in pan-spatial information system. Also, we present the new techniques which use memory computing to realize the storage-computing integration in vector spatial analysis.

Key words： geographic information system; vector spatial analysis; parallel computing; pan-spatial information system; spatio-temporal objects of multi-granularity; storage-computing integration

1 引言

全空间信息系统是一种对动态、复杂现实世界中各类时空实体信息进行综合管理,构建现实与数据关联的信息系统[1-2]。在全空间信息系统中,空间分析（Spatial Analysis）提供了强大的数据分析功能,由已知空间数据通过位置计算、属性继承和统计分析等方式,产生信息量更加丰富的空间数据。随着应用需求的提高和空间数据获取方式的进步,空间分析作为传统地理信息系统（Geographic Information System, GIS）和全空间信息系统的核心功能,面临对大规模空间数据的处理能力的全新挑战。
大数据时代中,80%的数据与空间位置有关[3]。急剧增长的地理空间数据已经成为大数据流的重要组成部分[4]。与一般数据相比,空间数据具有空间性、时间性、多维性、大数据量、空间关系复杂等特点[5]。近年来,随着对地观测领域中遥感图像的采集精度不断提高,测绘手段的日益丰富,地理数据的数据规模不断扩大。例如美国的对地观测系统（Earth Observing System,EOS）和其他对地观测平台每天将超过115 TB的速度产生海量影像数 据[6]。此外,随着移动互联技术的蓬勃发展,移动互联网用户的签到数据以及GPS定位等包含地理信息要素的数据规模大幅增长,数据类型日益丰富,并表现出数据价值实时性的特征。以百度为例,截止到2016年12月,百度地图每天有超过60万个APP及网站提供各种基于位置、导航、轨迹等LBS相关服务,每天位置服务次数突破720亿[7]。
“互联网+”空间大数据应用对空间分析提出了实时化要求。并行计算等技术在提高矢量空间分析算法性能中的研究成为热点。并行计算机源于上世纪70年代,在上世纪90年代系统结构框架趋于统一[8]。并行计算技术的发展与GIS相似,是在应用需求的推动下逐渐进步的。大量的实际应用场景,如天气预报、石油勘探、地震分析与预测、舆情监控等都需要计算能力能够达到每秒数十万亿次甚至更高的浮点运算。但是,单核处理器的主频提高范围有限,远不能达到这种需求,因此计算机的内核开始向着更多的方向发展,并行计算机成为解决大规模计算需求问题的发展方向。在硬件方面,当前世界上主流的超级计算机多以并行计算机为基础[9],这为并行空间分析算法实现提供了硬件基础。软件方面,并行空间计算编程技术的发展则面临诸多技术难点,例如空间数据结构复杂,并行空间分析编程难度较大;并行编程模型较多,实现手段多样化;以及面向空间计算的并行算法编程工具不够成熟等。
总体来讲,在全空间信息系统下,空间数据的发展体现出数据规模海量化,结构复杂化,价值实时化的发展特点[10]。在全球气候分析、国土资源利用、国防建设、社会应急救援等多个传统应用领域和金融业、保险业、现代服务业等新兴应用领域,空间分析技术将发挥不可或缺的重要作用。特别是以矢量数据为分析对象的空间分析算法在空间对象表达,存储空间压缩和分析精度提升上具有较多优势,是并行空间分析算法研究的重点。因此,GIS空间分析技术不断激发着专家学者们的研究热情。
本文将从应用需求和技术推动的角度回顾矢量空间分析的发展背景;从并行算法关键技术瓶颈、编程模型、空间数据存取和并行研发流程的角度总结并行矢量空间分析的研究成果;对全空间信息系统中基于多粒度时空对象模型的矢量空间数据并行计算方法的发展趋势进行了预测和分析。

2 矢量空间分析并行化研究背景

矢量空间分析并行化研究的两大推动力分别是应用需求和技术革新。一方面应用需求的提高对空间分析的精度和效率提出了更高要求,另一方面并行计算等技术的发展为矢量空间分析算法研究提供了更丰富的可行性方法。

2.1 应用需求推动

空间分析最早是在地图制图学和测量学中发展起来的,从处理简单要素之间的集合操作以及属性继承,发展到处理复杂地理空间要素之间的空间关系问题。
随后伴随着空间分析功能的完善和发展,空间分析在许多复杂应用场景中得到了广泛应用,例如住房选址问题中,空间分析能够利用兴趣点,道路交通信息,商业地产分布信息等不同类型不同属性的信息进行综合分析,为购房者提供住房选址参考;又如物流配送问题中,空间分析可根据货源地址,配送车辆以及道路交通等信息,规划合理的配送路线。在这些应用场景中都会涉及多个空间分析中的算法,根据基础算法功能的不同,可以构建解决某一类问题的算法流程,例如以缓冲区的输出结果作为下一步叠加分析的输入条件,从而快速解决流程复杂的空间分析问题。此外,空间分析不再局限于地理信息科学,在很多其他科学领域都得到了发展和应用。例如生态学中的物种空间分布,流行病学中的传染病传播情况,经济学中地域经济影响要素分析等。随着移动互联网的兴起,移动终端用户随时随地可以分享自己的位置信息并得到基于位置信息的各类服务,也就是LBS（Location Based Service）。GIS的系统架构经历了由大型机GIS到桌面GIS,网络GIS和分布式GIS的过程（图1）,空间分析方法更加丰富,应用场景也更加广泛。空间分析的用户特征也正在逐步从地学专家向各个科学领域专家,再到社会大众的方向逐步 发展。
Fig. 1 Development history of GIS

图1 GIS发展历程

2.2 计算技术推动

空间分析技术的发展经历了由简单问题暴力求解,到复杂数据结构和算法的设计,再到通过并行计算等技术提高算法效率的过程。以叠加分析为例,在20世纪70年代末,Shamos和Hoey开创性的提出了平面扫描技术来快速求解线段相交问题[11]。该方法可以利用一条平面扫描线通过一次过滤快速的计算线段之间的交点,从而取代了原本线段求交问题中的暴力求解方法,大大提升了线段求交的效率。Bentley和Ottmann随后对该方法进行了优化和改进,因此扫描线算法也称为BO算法[12]。此后,出现了大量的科研成果基于该算法思想对该算法进行了优化和改进[13-15]。随着扫描线算法的成熟,叠加分析算法大多采用了扫描线算法的思想[16-17],在使用扫描线算法进行线段求交运算的基础上,研究人员又利用空间索引技术来快速定位线段相交位置,进而提高叠加分析的整体效率[18-20]。至此,空间分析的串行算法研究已经相对成熟,优化数据结构和算法等传统研究方法难以对算法效率提供突破性进展。而硬件方面,计算机单核处理器的主频提升空间有限,高性能计算机多采用多核处理器的方式来提升计算能力。
在20世纪90年代末和21世纪初,GIS领域已经出现了基于并行计算模式的并行空间分析算法研究[21-22]。但是受限于计算机硬件和并行计算技术,并行空间分析在很长时间内没有取得突破性进展。当前,中国GIS以及空间分析算法迎来了新的发展契机[1]。现有研究成果基于高性能计算机平台,提出了串行算法的并行改造、并行算法性能提升和并行算法创新设计等,进而研发了面向新型硬件架构的新一代GIS基础地理并行计算算法库和中间件,提高GIS的整体服务性能[23]。随着全空间信息系统概念的提出,以多粒度时空对象的全生命周期管理为目标的空间分析将成为进一步研究的热点[2]。
总体而言,矢量空间分析技术的进步是在空间数据和应用需求的促进下逐步发展的,从简单要素的暴力求解,到复杂数据结构和算法的设计,不断降低算法复杂度,提高算法性能。随着并行计算机的发展,利用并行计算等技术解决大规模空间要素的分析问题成为新的发展方向。

3 并行矢量空间分析研究现状

并行计算技术是实现高性能GIS的重要技术手段。在GIS的并行化研究现状中,本文总结了3个主要的研究方向（表1）。① 空间数据的并行处理,针对空间数据模型和空间索引机制进行并行化研究,提高空间数据的查询和访问性能。② 并行空间分析,根据具体空间分析算法特征,采取合适的并行化方法优化算法效率。该研究方向又细分为3种研究思路。细粒度的算法并行化研究是针对空间分析的算法过程进行并行化改造,优化数据结构,提高可并发性;粗粒度的并行话研究是基于任务级并行,对参与分析的空间数据进行合理划分,通过任务调度实现并行计算的总体目标;并行框架研究是采用统一的并行算法编程模型,在不改变原有算法结构的基础上通过并行计算框架,快速完成算法并行化改造,提升算法研发效率。③ 并行空间数据库研究,在数据库中提升空间数据的并发读写性能。
Tab. 1 Research status of parallel GIS

表1 并行GIS研究现状

研究方向 代表性研究 研究成果
空间数据并行处理 Richard Healey和Steve Dowers基于文件系统对空间数据条带化处理[21] 基于MIMD体系结构的原型系统和函数库
易法令等提出的空间数据格式转换算法[24] GRID、TIN格式转换算法和任务调度
Hoel和Samet并行空间索引[25] 基于四叉树、R树和R+树的并行索引
HadoopGIS[26]和GeoSpark[27] 利用Hadoop及Spark等计算架构完成空间数据的并行检索
细粒度算法并行化 Lanthier[28]等最短路径算法,张丽丽[29]平面扫描算法 并行空间分析基础算法
粗粒度任务并行 McKenney[30]等并行扫描线算法 为任务级并行空间分析提供了理论基础
Agarwa[31]等提出了overlay算法并行策略;范俊甫[32-33]用MPI并行方法研究多边形合并及缓冲区算法 基于Linux集群的并行overlay算法
空间分析并行框架 Dowers[34]和Mineter[35]矢量拓扑并行处理框架 用开放式GIS服务架构兼容的软件组件,进行并行拓扑构建
Qin[36]等提出的栅格空间分析并行框架 实现不同算法不同并行策略下的并行编程框架
并行空间数据库 Zhao[37]利用面向对象模型实现空间数据描述;
陈达伦等[38]提出了基于MPP架构的并行空间数据库		 并行GIS数据库平台

3.1 并行矢量空间算法特征和关键问题

深入理解矢量空间分析算法过程,研究算法原理可知算法存在数据敏感、空间拓扑和计算密集与数据密集的特征。
（1）数据敏感特征
多数矢量空间分析算法属于输入敏感型算法,即算法的效率受输入数据影响较大。输入数据图层的要素数量、空间关联性以及单一要素的分布特征均会对算法效率造成较大影响。例如,在线段相交算法中,首先会针对两组输入的线段进行相交判断,存在交点的线段执行求交运算,不存在交点的线段执行过滤操作。相交计算与过滤操作的时间复杂度差异较大,因此线段求交算法的计算时间与输入数据的交点个数相关。在具体分析任务开始前无法预知参与运算的空间数据的分布特征,因此造成算法效率的不可预估性。
（2）空间拓扑特征
在空间分析算法中,对空间对象的操作不能破坏空间数据的基本拓扑结构。在并行算法设计时,常用的方法是基于任务级的数据划分,在矢量空间数据的划分时,一方面要尽量不破坏空间要素之间的拓扑关系,保证位置临近的空间要素被分配到同一计算任务中。另一方面不能简单的依照坐标系的坐标范围将空间数据按照空间区域切分,数据划分的基本原则是要保证空间数据的拓扑完整性,因此在矢量数据的划分中数据原子是最小的划分单元。空间拓扑特征的存在导致数据划分结果在数据量上存在差异性,是导致并行算法负载不均的主要原因之一。
（3）计算与数据密集特征
由于真实地理数据空间要素数量多,结构复杂,在分析处理过程中需要大量计算时间,已有研究成果大多关注计算密集特征,另一方面,多数空间分析方法为全局计算,即输入的空间数据需要全部读入内存参与运算,存在明显的数据密集特征。对于部分空间分析算法,如叠加分析求并操作,部分运算结果产生的空间要素规模甚至比输入图层中要素规模更大,因此空间数据的I/O时间在算法整体执行时间中将占据较高的比例。在计算并行算法效率时,随着参与计算任务的计算节点数目增多,空间分析的计算部分时间会逐步减少,而I/O时间所占算法总时间比例将持续增大,成为整体算法的性能瓶颈。因此并行算法设计应同时考虑算法的计算密集与数据密集的特征。
结合并行矢量空间分析算法特征,并行矢量空间分析技术的发展面临如下2个关键性能瓶颈：
（1）并行任务负载不均：基于现有数据模型,矢量空间分析无法在计算任务开始前预知参与计算的空间对象的分布情况,因此数据划分等预处理操作会产生并行任务负载不均的情况。
（2）数据通信成本过高：由于矢量空间分析的数据密集特征,在计算过程中,进程通信造成了不可避免的时间消耗,制约了并行算法的扩展性。一方面是不同进程之间交换数据需要大量的I/O操作,另一方面是空间数据模型在数据通讯时进行的序列化与反序列化操作效率较低,成为数据通信中的主要性能瓶颈。
本文作者通过理论研究与实验验证,已经提出了并行叠加分析中的3个关键技术问题[39],分别是矢量空间分析的并行化方法,矢量空间数据划分以及矢量空间数据存取技术。针对这些技术问题,本文作者[40-41]在服务器集群环境中进行了叠加分析并行算法设计与实现,通过动态树形归并等策略提升并行算法效率。随后,本文作者[42]针对矢量空间数据划分问题进行研究,提出了一种基于空间聚类思想的数据划分方法,该方法在确保空间邻近性原则的前提下通过空间填充曲线完成并行算法中数据任务的划分,在确保计算任务负载均衡性的同时有效提升了子进程任务的效率。

3.2 并行算法不同编程模型对比

赵艳伟等[43]提出了一种基于CUDA的并行叠加分析算法。该方法利用GPGPU在多线程计算方面的性能优势,将IDW算法映射到CUDA架构,与CPU计算方法对比取得了更好的加速比,但空间数据传输受总线带宽影响。李峙等[44]针对CAD图像转换成GIS数据的叠加分析需求,以四叉树索引的形式实现了点面叠加分析的并行化处理过程。朱效民[45]提出了一种基于OpenMP的线段求交及点面叠加并行算法,该方法通过数据排序及动态调度对点面关系的计算取得了接近理想加速比的效果。Agarwal[31]等基于MPI消息传递的方式在Linux集群中进行了并行叠加分析性能试验,此后随着MapReduce计算框架的兴起,产生了许多基于Hadoop平台的空间分析方法[46-47]。Puri等[48]基于MapReduce思想研究并行叠加分析算法,算法并行效率进一步提升,但该方法仍然不可避免MapReduce架构特性带来的多次磁盘操作对并行效率的影响。Salles等[49]提出了一种没有摄入误差的并行算法：EPUG-overlay,该方法使用二级网格结构使得算法在分均匀的数据集上表现良好。
以上研究成果基于不同的并行编程模型,采取了不同的并行变成策略,在并行化力度,性能特点及适用场景等方面存在各自特点。本文针对并行矢量空间分析常用编程模型进行了归纳总结,如表2所示。在并行粒度方面,OpenMP和CUDA采用线程级细粒度并行,MPI和MapReduce为进程级粗粒度并行。在性能特点上,OpenMP基于共享内存完成算法并行化编程,实现较为简单,且并行算法效率较高。但是共享内存模式只适用于SMP等并行环境,无法应用到集群环境中,并行算法扩展性较差,因此该方法适用于空间分析算法的局部优化。MPI通过消息传递完成进程级的任务划分和通讯,并行算法设计的灵活性较高,在集群环境中扩展性较好,缺点是如果某一进程出现异常则整个并行算法将执行失败,算法的容错性较差。MapReduce具有完善的容错机制,当某一计算任务异常时调度节点会记录任务状态并重新分发任务。但是针对空间分析的应用场景,MapReduce任务分发机制相对复杂,且中间结果的存储增加了磁盘I/O的负担。CUDA的最大优势是浮点计算能力,在并发执行计算任务时有明显的效率优势,但是在矢量空间数据通讯时数据的传输效率较低,成为制约算法效率的性能瓶颈,因此CUDA更适用于计算密集且非数据密集的算法。
Tab. 2 Comparison of parallel programming models for vector spatial analysis

表2 矢量空间分析并行编程模型对比

并行编程模型 OpenMP MPI MapReduce/Spark CUDA
并行粒度 细粒度 粗粒度 粗粒度 细粒度
性能优势 实现简单,并行效率高 适用于集群环境,并行算法扩展性强 编程实现简单,容错性好 强大的并行浮点计算能力
缺点 只适用SMP等并行环境,扩展性差 容错性差 中间结果存储造成I/O次数增多 空间数据传输效率低,算法普适性低
适用GIS场景 空间分析算法的局部优化 高性能并行空间分析算法研发 数据密集型空间操作 计算密集型空间操作

3.3 空间数据存取技术研究

算法数据密集型特征的影响越来越明显,使得研究工作者越来越多的开始关注空间数据通信性能对算法整体效率的影响。近年来,随着存储空间和内存容量变得越来越廉价,内存数据库中数据持久化与容错技术相对成熟,以内存设备管理空间数据提高空间分析算法的数据I/O性能成为新的发展趋势。在信息技术领域的发展中,内存计算技术在数据密集型算法应用中发挥着重要作用。目前,内存数据库技术和内存计算技术得到广泛发展,如SAP推出的HANA以及Apache的Spark,都是解决内存计算中高性能数据存取技术的有效方案。本文综合分析内存计算技术与矢量空间分析算法特征,结果如表3所示。
Tab. 3 Characteristic comparison between memory database and vector spatial analysis

表3 内存数据库与矢量空间分析特征对比

内存数据库 矢量空间分析算法I/O
读写性能 数据常驻内存,读写速度快的key-value数据结构 数据密集特征,I/O时间成为制约算法效率的性能瓶颈
存储容量 存储容量存在上限,超过内存限制会大量使用swap,降低性能 以矢量数据为存储模型,表达空间对象信息丰富,但数据规模较小
持久化 安全稳定的持久化策略 对空间数据存储和系统容错有较高要求
Master-Slave复制 适合集群应用环境 在集群环境中,通过并行计算技术提高算法效率
分析认为,内存数据库在读写性能、持久化以及集群应用等方面非常适合于矢量空间分析算法的I/O操作应用,并且在数据特征上,矢量空间数据是以较小的数据规模表达较为丰富的空间对象信息,非常适合轻量级数据管理的特征。利用内存数据库管理空间数据能够有效提高不同内存空间数据交互效率,并且能够借鉴空间查询算法的研究思路,在数据的索引阶段将不存在相交关系的空间要素进行过滤,降低空间分析的计算量,能够达到存储与计算一体化的服务效果。
朱进等[50]提出了一种基于Redis的矢量数据组织形式,以NoSQL数据库在空间查询效率的优势方面与传统SQL数据库做出对比,实现了空间数据查询在NoSQL数据库中的应用。张景云[51]提出了一种利用Redis管理轻量级矢量空间数据的方法,该方法在内存数据库中以hash形式管理空间要素,并以set数据类型管理矢量图层,实现了矢量空间数据在内存数据库中的分层管理。Liu等[52]提出了一种在分布式内存环境中的空间哈希（Geohash）[53]索引,用于管理空间数据,进而提高空间分析等操作中空间数据的访问效率,该方法与PostgreSQL数据库对比有明显效率提升。Zhao等[54]针对数据密集型的空间分析运算,提出了一种基于分布式环境的空间数据管理框架：Robinia DSSSD（Distributed Storage and Service for Spatial Data）,该方法以干旱监测算法为测试对象,能够在低负载情况下有效加快数据访问速度,对数据密集型计算提供了支持。Zhang等[55]提出了一种HBase中的空间数据存储模型,与MongDB、MySQL对比,不同类型空间数据的查询速度取得明显提升。姚晓等[56]提出了一种全内存的矢量空间数据存取技术。该技术针对叠加分析等算法在计算过程中数据访问效率低的性能瓶颈,采用内存数据库管理参与分析任务的热点矢量空间数据,以内存拷贝的形式取代传统方法中从外存设备向内存读写数据的操作,大大提升了矢量空间数据的访问效率,特别是在并行算法中,对子进程多次访问数据源性能提升具有重要意义。

3.4 并行矢量空间算法流程

结合并行矢量空间分析算法特征,本文阐述了并行矢量空间分析在计算过程和I/O过程的研究成果,可以总结并行矢量空间分析算法的设计流程如图2所示。
Fig. 2 Research and development process of spatial analysis of parallel vector

图2 矢量空间分析并行算法研发流程

（1）在需求分析阶段,依据空间分析的2个主要应用需求,分析空间分析算法的适用场景。空间大数据分析需要处理海量空间数据,要求分析算法具备较强的数据吞吐能力,能够适应计算密集和数据密集的算法特征,具备较强的算法精度。移动互联网环境中的实时空间分析对算法效率要求较高,需要针对用户发出的空间分析请求进行快速响应,满足实时化应用需求。
（2）在算法分类阶段,根据需求分析结果对现有空间分析算法进行性能测试,提取具有性能瓶颈的空间分析算法作为主要研究对象。算法分析阶段主要工作是算法特征提取。矢量空间分析算法由于参与计算的图层类型,数量以及输出结果的种类等差别具有不同的算法特征,如计算密集型、数据密集型、I/O密集型。部分算法还具有多种算法特征的组合特征。将算法进行分类有利于对不同类型算法采取针对性优化方案。
（3）在优化策略阶段,主要包括并行策略分析和选择以及矢量空间数据存取技术优化2个方面。在并行策略分析和选择方面,依据具体空间分析算法的特征,采取不同的并行优化策略,如共享内存方式,消息传递方式,多线程加速方式等。矢量空间数据存取技术方面,最新研究成果采用内存数据库管理参与空间分析的热点数据,实现内存数据库中空间数据类型的扩展。在空间分析的I/O阶段,以内存拷贝的形式取代传统算法从磁盘读取空间数据的操作,达到优化算法效率的目的。
（4）算法设计阶段,针对粗粒度的并行策略,如MPI、MapReduce等,将采用统一的并行编程框架,提高算法并行化编程效率。针对细粒度的并行策略,如OpenMP、CUDA等,将根据不同算法特征,设计并实现具体的并行化算法。
（5）在算法实现阶段,采用中间件开发与测试方法一次实现矢量空间分析算法工具集,并对研发的算法中间件进行性能测试与评估。对无法满足应用需求,存在明显性能瓶颈的算法进行重新优化,依次迭代技术路线过程,直至达到应用需求。

4 全空间下空间分析技术发展趋势

4.1 多粒度时空对象发展

在大数据时代背景下,地理数据的获取方式发生了翻天覆地的变化。随着智能手机等终端设备和app的广泛应用,GIS用户不再只是数据的使用者,同时也是数据的生产者。GIS数据可以是移动用户基于GPS的签到信息,可以是wifi热点的采集信息,也可以是基于自然语言描述,经过空间数据挖掘获取的包含语义信息的位置信息。在这种模式下GIS数据的获取速度更快、信息量更大、数据更新更迅速、数据类型也更加复杂。
从目前的矢量空间分析方法和未来需求分析来看,矢量空间分析大致会向着2种不同的需求类型发展。第一类是大数据分析。矢量空间数据的数据规模会进一步扩张,数据集合信息会更加复杂,所包含的属性信息也会更加丰富。在这种背景下,要求空间分析方法能够具备短时间内精确处理空间大数据的能力,为国土资源、测绘分析、气象预测和空间数据挖掘等应用提供有力支持。另一类是多粒度时空数据的实时处理。空间数据在未来发展中具备更强的时效性,时间属性将在空间分析方法中起到关键作用。因此,需要未来的空间分析方法能够快速灵敏的对各种分析需求做出响应,实现“秒级”计算。
在全空间信息系统中,空间数据类型更加丰富,时空轨迹数据、交互数据、三维数据等多样化的数据类型将丰富空间分析的方法。面对大数据类型多、空间关联性强、实时性强等特点,传统的基于离散式的数据描述面临挑战。基于OGC标准的点、线、面等基本空间几何对象不足以表达各种应用领域内对空间数据的需求。因此,从本质上提升空间分析效率需要在矢量空间数据结构上实现突破性创新。而多粒度时空数据模型以空间实体为描述对象,是未来空间分析中重要的研究方向。多粒度时空数居模型主要内容包含：
多粒度时空对象=<时空参考,空间位置,空间形态,组成结构,关联关系,认知能力,行为能力,属性特征>。
与传统OGC模型不同,在多粒度时空对象模型中,以八元组进行空间对象的描述和刻画,突破了传统点、线、面基本类型。在不同的应用场景中,空间对象具备不同的描述粒度,对象可以灵活的进行组合与分解,实现多粒度表达。因此,传统数据模型的数据敏感、拓扑结构复杂以及计算密集等特征所造成的负载不均、通讯成本高等性能瓶颈才有望在技术原理上得到突破。
因此,多粒度时空数据模型可以在具体应用场景中,构建相应的地理数据模型从而处理高复杂度地理对象。在该应用场景下,为满足空间分析的秒级响应需求,要求传统空间分析中计算任务能够更多的在数据存储端完成,如数据编码、降维、索引等预处理操作,将计算任务转换为多粒度时空对象中多维度的表达,从而降低计算任务量,达到存算一体化的效果。
目前,传统数据模型下并行空间分析算法已经有一定的研究基础。并行计算、内存计算、分布式存储等技术在信息技术领域已经相对成熟,为全空间信息系统中基于多粒度时空对象的分布式存储和分析提供了技术保障。从并行空间分析的应用需求来看,全空间信息系统中多粒度时空对象模型需要具备如下特点：
（1）丰富的数据类型。除了支持传统GIS数据模型外,还应该支持动态的、连续变化的时空数据、流式数据、以及不间断观测数据等。
（2）简单化的基本数据单元。该数据单元包含空间数据的基本数据特征,在不同的应用场景中具有不同比例尺和维度的描述方式,可以分布式存储于文件系统,在并行计算环境中具备高并发性。
（3）高效的内存与外存交互方式。满足数据在内存和外存设备中的一致性,实现空间数据在不同内存空间的快速拷贝,从而提高数据交互效率。
（4）具有空间临近性特征的数据存储方式。依据地理数据越临近越相关的特性,通过空间索引等确保并行空间分析中临近数据相对集中在同一任务中,从而解决各个计算节点负载平衡问题。
（5）具有高扩展性。多粒度时空数据模型应当具有高度扩展性,同时支持类型缺省,突破数据类型、文件大小等限定,可以适应大数据时代海量空间数据无限扩展的需求,可以满足不同领域GIS用户数据定制的要求,构建复杂地理对象的结构共享体。

4.2 并行矢量空间分析算法发展

从全空间信息系统中空间分析的发展趋势来看,空间数据的价值体现在数据的共享。空间数据的获取方式将产生很大的变化,这其中涉及数据采集的质量问题,数据更新的增量计算问题以及数据合法性的验证问题等。此外,如前文所述,用户对空间分析算法的性能需求不断提高。在未来并行矢量空间分析算法发展中存在几个关键技术问题：
（1）提高并行算法负载均衡度。基于多粒度时空对象,针对空间数据的分布特征,在数据存储端通过有效的索引机制完成数据划分等预处理工作,充分利用多粒度时空对象存储丰富,结构灵活的特点,提高并行算法负载均衡度,进而提升并发扩展性。
（2）提升空间数据存取性能。以并行文件系统、内存计算等技术提高并行空间分析算法中大规模空间数据的存取性能。如前文所述,矢量空间分析存在数据密集特征,提高空间数据的访问效率能够有效提升并行空间分析算法的整体性能。多粒度时空对象应具备对NoSQL等非结构化数据形式的支持,提升内外存数据转换效率。目前,HDFS（Hadoop Distributed File System）等分布式文件系统,以及HANA、Spark等内存计算技术都可以在空间分析领域进行借鉴和发展。
（3）实现鲁棒高效的复杂空间分析算法工作流。全空间信息系统中空间分析的应用需求必然向着流程复杂化、计算智能化、性能实时化的方向发展。未来工作流应当以典型空间分析方法为基础算法,快速构建复杂的空间分析工作流,在高性能的计算机环境中,以深度机器学习技术智能分配计算资源,为复杂空间分析任务分配合理的计算节点数量,从而得到多源数据的综合分析结果。

5 总结

传统地理信息系统中,矢量空间分析算法研究存在数据结构复杂,负载不均,数据访问效率低等技术难点。但是矢量数据格式具有数据表达准确、存储空间小、内容丰富等优势。因此,并行矢量空间分析在未来发展中成为技术难点的同时也将成为研究工作的热点。特别是在全空间信息系统概念中,空间分析所面临的空间对象种类,数据规模,分析方法,都将出现翻天覆地的变化,但空间分析技术的发展方向仍然有迹可循。
本文从应用需求和技术发展的角度回顾了矢量空间分析算法的发展历史和现状;总结了目前并行矢量空间分析的研究成果,在大数据时代背景下的并行空间分析仍面临负载平衡、通讯代价等问题;在新一代全空间信息系统的空间分析展望方面,根据数据模型特征和算法特征做出了总结和预测,对研究全空间下并行矢量空间分析算法具有参考价值。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
周成虎. 全空间地理信息系统展望[J].地理科学进展,2015,34(2):129-131.地理信息系统作为一门空间科学,以其独特的空间观点和空间思维,从空间相互联系和相互作用出发,揭示各种事物与现象的空间分布特征和动态变化规律。本文从地理信息系统所研究的空间对象出发,对地理信息系统发展新方向提出思考：①从地球空间拓展到宇宙空间,需要构建宇心坐标系和宇宙GIS、月球GIS等;②从室外空间延伸到室内空间,需要发展室内GIS,并拓展到水下空间和地下空间;③从宏观到微观空间,可以发展面向游戏的体育GIS、面向生命健康管理的人体GIS等;④面向大数据时代,发展大数据空间解析的理论和方法,贡献于大数据科学的发展。

DOI

[Zhou C H.Prospects on pan-spatial information system[J]. Progress in Geography, 2015,34(2):129-31. ]

[2]
华一新. 全空间信息系统的核心问题和关键技术[J].测绘科学技术学报,2016,33(4): 331-335.分析了空间信息系统的研究现状和存在问题,阐明了全空间信息系统的基本概念和基本特征;提出了基于多粒度时空对象构建全空间信息系统的技术路线,明确了需要研究解决的科学问题和关键技术;提出了全空间信息系统与智能设施管理的主要研究内容,指出预期的研究效益。

DOI

[Hua Y X.The core problems and key technologies of pan-spatial information system[J]. Journal of Geomatics Science and Technology[J]. Journal of Geomatics Science and Technology, 2016,33(4):331-335. ]

[3]
Shekhar S, Xiong H.Encyclopedia of GIS[M]. Berlin: Springer, 2008.

[4]
张晓祥. 大数据时代的空间分析[J].武汉大学学报·信息科学版,2014,39(6):655-659.

[Zhang X X.Spatial analysis in the era of big data[J]. Geomatics and Information Science of Wuhan University, 2014,39(6):655-659. ]

[5]
王树良,丁刚毅,钟鸣.大数据下的空间数据挖掘思考[J].中国电子科学研究院学报,2013,8(1):8-17.对大数据背景下思考空间数据挖掘，分析了空间数据在大数据中的基础地位，综述了国际学术界、企业界和政界对大数据的关注；分析了空间大数据面临的垃圾多、污染重、利用难的现状，剖析了空间大数据蕴含的价值；探讨了从空间大数据中挖掘知识的技术，以及知识变为数据智能的途径。

DOI

[Wang S L, Ding G Y, Zhong M.On spatial data mining under big data[J]. Journal of China Academy of Electronics and Information Technology, 2013,8(1):8-17. ]

[6]
Yang R, Yang K S, Kafatos M, et al.Value range queries on earth science data via histogram clustering[M]. Temporal, Spatial, and Spatio-Temporal Data Mining. Berlin:Springer, 2001:62-76.

[7]

[8]
张林波. 并行计算导论[M].北京:清华大学出版社,2006.

[Zhang L B.Introduction to parallel computing[M]. Beijing: Tsinghua University press, 2006. ]

[9]
迟学斌.高性能并行计算[M].2005. https://wenku.baidu.com/view/ 52aa1ba8bb4cf7ec4bfed003. html.

[Chi X B, High performance parallel computing[M].2005. https://wenku.baidu.com/view/52aa1ba8bb4cf7ec4bfed003.html

[10]
李德仁,王树良,李德毅.空间数据挖掘理论与应用[M].北京:科学出版社,2006.

[Li D R, Wang S L, Li D Y.Theory and application of spatial data mining[M]. Beijing Science Press, 2006. ]

[11]
Shamos M I, Hoey D. Geometric intersection problems. Proceedings of the Foundations of Computer Science, 1976,17th Annual Symposium on, F, 1976[C]. IEEE.

[12]
Bentley J L, Ottmann T A.Algorithms for reporting and counting geometric intersections[J]. Computers, IEEE Transactions on, 1979,100(9):643-647.An interesting class of "geometric intersection problems" calls for dealing with the pairwise intersections among a set of N objects in the plane, These problems arise in many applications such as printed circuit design, architectural data bases, and computer graphics. Shamos and Hoey have described a number of algorithms for detecting whether any two objects in a planar set intersect. In this paper we extend their work by giving algorithms that count the number of such intersections and algorithms that report all such intersections.

DOI

[13]
Nievergelt J, Preparata F P.Plane-sweep algorithms for intersecting geometric figures[J]. Communications of the ACM, 1982,25(10):739-47.ABSTRACT An abstract is not available.

DOI

[14]
Chazelle B, Edelsbrunner H.An optimal algorithm for intersecting line segments in the plane[J]. Journal of the ACM (JACM), 1992,39(1):1-54.The main contribution of this work is an O(n log n + k)-time algorithm for computing all k intersections among n line segments in the plane. This time complexity is easily shown to be optimal. Within the same asymptotic cost, our algorithm can also construct the subdivision of the plane defined by the segments and compute which segment (if any) lies right above (or below) each intersection and each endpoint. The algorithm has been implemented and performs very well. The storage requirement is on the order of n + k in the worst case, but it is considerably lower in practice. To analyze the complexity of the algorithm, an amortization argument based on a new combinatorial theorem on line arrangements is used.

DOI

[15]
Balabran I J. An optimal algorithm for finding segments intersections[C].Proceedings of the eleventh annual symposium on Computational geometry,F, 1995,ACM.

[16]
毛定山. 基于计算几何的矢量数据叠加分析算法研究[D].济南:山东科技大学,2007.

[Mao D S.Research on vector data overlay analysis algorithm based on computational geometry[D]. Jinan: Shandong Technolgy Univeristy, 2007. ]

[17]
张文艺. GIS 缓冲区和叠加分析[D].长沙:中南大学, 2007.

[Zhang W Y.GIS buffer and overlay analysis[D]. Changsha: Central South University, 2007. ]

[18]
董鹏. 分布式空间信息的高效查询与分析系统研究[D].北京:中国科学院遥感应用研究所,2003.

[Dong P.Research on efficient query and analysis system of distributed spatial information[D]. Beijing: Institute of remote sensing applications, Chinese Academy of Sciences, 2003. ]

[19]
朱效民,赵红超,刘焱,等.矢量地图叠加分析算法研究[J].中国图象图形学报,2010,15(11):1696-706.提出了一整套矢量地图叠加分析算法：提出了大量点与多边形关系的包含性测试方法，首先对多边 形进行预处理，然后采用射线法对单个点进行包含性测试；提出了基于双索引的大量线裁剪方法，分别以线、线段为基础建立两层索引，有效去除不必要的求交运 算；面面叠加，基于改进的扫描线方法求取交点；通过对过同一点的线段分布情形的完备分类，涵盖了所有特殊类型的交点；在构造环的过程中，保存整型ID信 息，并利用ID完成内环外环的匹配以及属性继承。以上几何计算方法及对应的叠加分析功能都已经实现，与最新研究成果的对比以及与ArcGIS对应功能的对 比，都证明了其正确鲁棒、高效可用。上述实现已经应用于实际的GIS系统中，取得了良好的效果。

DOI

[Zhu X M, Zhao H C, Liu Y, et al.Research on vector map overlay[J]. Journal of Image and Graphics, 2010,15(11):1696-706. ]

[20]
朱效民,赵红超,方金云.鲁棒高效的矢量地图叠加分析算法[J].遥感学报,2012,16(3):448-465.提出了一个鲁棒高效的内存矢量地图叠加分析算法,采用改进的平面扫描算法计算交点,解决了重叠边、交点位于端点等所有特殊情形。利用交点及其携带的信息来构造结果环,并且将没有产生交点的输入环忽略,或者增加到结果的外环(或内环)集合中去。所有结果环都带有标识码,增加该标识码信息可以简化后续的两个过程-内外环的匹配以及属性的继承。与一一循环方法相比,本文方法对任何叠加操作可以一次计算得到所有的交点。此外还实现了叠加分析操作,并且用一组真实地理数据的不同操作与ESRI的ArcGIS的叠加分析操作进行了比较,计算结果的要素数完全一致;计算时间耗费约为ArcGIS时间耗费的50%-60%。

DOI

[Zhu X M,Zhao H C, Fang J Y.A robust and efficient method for vector map overlay[J]. Journal of Remote Sensing, 2012,16(3):448-465. ]

[21]
Healey R, Dowers S, Gittings B, et al.Parallel processing algorithms for GIS[M]. Abingdon: Taylor and Francis, 1998.

[22]
Clematis A, Mineter M, Marciano R.High performance computing with geographical data[J]. Parallel Computing, 2003,29(10):1275-1279.The delivery of multimedia over the Internet is affected by adverse network conditions such as high packet loss rate and long delay. This paper aims at mitigating such effects by leveraging client-side caching proxies. We present a novel cache architecture and associated cache management algorithms that turn edge caches into accelerators of streaming media delivery. This architecture allows partial caching of media objects and joint delivery from caches and origin servers. Most importantly, the caching algorithms are both network-aware and stream-aware; they take into account the popularity of streaming media objects, their bit rate requirements, and the available bandwidth between clients and servers. Using Internet bandwidth models derived from proxy cache logs and measured over real Internet paths, we have conducted extensive simulations to evaluate the performance of various cache management algorithms. Our experiments demonstrate that network-aware caching algorithms can significantly reduce startup delay and improve stream quality. Our experiments also show that partial caching is particularly effective when bandwidth variability is not very high.

DOI

[23]
吴立新,杨宜舟,秦承志,等.面向新型硬件构架的新一代 GIS 基础并行算法研究[J].地理与地理信息科学,2013,29(4):1-8.随着减灾应急、流域模拟、智能交通、宏观规划、区域发展等大型地 学问题的不断涌现,地理信息系统(GIS)处理的数据量和计算规模不断扩大,而主流GIS仍以串行计算为基础框架,不能充分利用和发挥当前新型硬件构架 (单机多核、多机多核、集群等)计算机资源的能力,难以满足实际应用的规模与高效需求.该文在分析了基础地理算法研究现状的基础上,按计算数据的关联性将 基础地理算法的计算特征分为本地计算、邻域计算、区域计算和全局计算,按计算过程的资源消耗分为数据密集型、计算密集型和I/O密集型,提出了相应的并行 计算策略,包括串行算法的并行改造、并行算法的性能提升和并行算法的创新设计等.进而研发了面向新型硬件构架的新一代GIS的基础地理并行计算算法库和中 间件,并已集成到国产高性能GIS平台——HiGIS中,将会促进我国GIS研究、技术、系统和应用的跨越式发展.

DOI

[Wu L X, Yang Y Z, Qin C Z, et al.On basic geographic parallel algorithms of new generation of GIS for new hardware architectures[J]. Geography and Geo-Information Science, 2013,29(4):1-8. ]

[24]
易法令,严圣华. GIS 空间数据格式并行转换的调度算法[J].计算机工程,2005,30(23):47-49.

[Yi F L, Yan S H.Scheduling algorithm of spatial data format parallel switch of GIS[J]. Computer Engineering, 2005,30(23):47-49. ]

[25]
Hoel E G, Samet H.Data-parallel polygonization[J]. Parallel Computing, 2003,29(10):1381-1401.

[26]
Aji A, Wang F, Vo H, et al.Hadoop GIS: A high performance spatial data warehousing system over mapreduce[J]. Proceedings of the VLDB Endowment, 2013,6(11):1009-1020.Abstract Support of high performance queries on large volumes of spatial data becomes increasingly important in many application domains, including geospatial problems in numerous fields, location based services, and emerging scientific applications that are increasingly data- and compute-intensive. The emergence of massive scale spatial data is due to the proliferation of cost effective and ubiquitous positioning technologies, development of high resolution imaging technologies, and contribution from a large number of community users. There are two major challenges for managing and querying massive spatial data to support spatial queries: the explosion of spatial data, and the high computational complexity of spatial queries. In this paper, we present Hadoop-GIS - a scalable and high performance spatial data warehousing system for running large scale spatial queries on Hadoop. Hadoop-GIS supports multiple types of spatial queries on MapReduce through spatial partitioning, customizable spatial query engine RESQUE, implicit parallel spatial query execution on MapReduce, and effective methods for amending query results through handling boundary objects. Hadoop-GIS utilizes global partition indexing and customizable on demand local spatial indexing to achieve efficient query processing. Hadoop-GIS is integrated into Hive to support declarative spatial queries with an integrated architecture. Our experiments have demonstrated the high efficiency of Hadoop-GIS on query response and high scalability to run on commodity clusters. Our comparative experiments have showed that performance of Hadoop-GIS is on par with parallel SDBMS and outperforms SDBMS for compute-intensive queries. Hadoop-GIS is available as a set of library for processing spatial queries, and as an integrated software package in Hive.

DOI PMID

[27]
Yu J, Wu J, Sarwat M.GeoSpark: A cluster computing framework for processing large-scale spatial data[C]. Proceedings of the Sigspatial international conference, F, 2015.

[28]
Lanthier M, Nussbaum D, Sack J R.Parallel implementation of geometric shortest path algorithms[J]. Parallel Computing, 2003,29(10):1445-1479.In application areas such as geographical information systems, the Euclidean metric is often less meaningfully applied to determine a shortest path than metrics which capture, through weights, the varying nature of the terrain (e.g., water, rock, forest). Considering weighted metrics, however, increases the run-time of algorithms considerably suggesting the use of a parallel approach. In this paper, we provide a parallel implementation of shortest path algorithms for the Euclidean and weighted metrics on triangular irregular networks (i.e., a triangulated point set in which each point has an associated height value). To the best of our knowledge, this is the first parallel implementation of shortest path problems in these metrics. We provide a detailed discussion of the algorithmic issues and the factors related to data, machine, implementation which determine the performance of parallel shortest path algorithms. We describe our parallel algorithm for weighted shortest paths, its implementation and performance for single- and multiple-source instances. Our experiments were performed on standard architectures with different communication/computation characteristics, including PCs interconnected by a cross-bar switch using fast ethernet, a state-of-the-art Beowulf cluster with gigabit interconnect and a shared-memory architecture, SunFire.

DOI

[29]
张丽丽. 支持空间分析的并行算法的研究与实现[D].南京:南京航空航天大学,2008.

[Zhang L L.Research and realization of parallel algorithm supporting spatial analysis[D]. Nanjing: Nanjing University of Aeronautics & Astronautics, 2008. ]

[30]
Mckenney M, Mcguire T. A parallel plane sweep algorithm for multi-core systems[C].Proceedings of the Proceedings of the 17th ACM Sigspatial International Conference on Advances in Geographic Information Systems, F, 2009.ACM.

[31]
Agarwal D, Puri S, He X, et al. A system for GIS polygonal overlay computation on linux cluster-an experience and performance report [C]. Proceedings of the Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International, F, 2012.IEEE.

[32]
范俊甫,马廷,周成虎,等.几何部件缓冲区域合并的 Buffer 算法及其并行优化方法[J].测绘学报,2014,43(9):969-975.lt;p>摘 要：本文在介绍一种基于几何部件缓冲区域合并的矢量数据缓冲区生成算法的基础上，采用数据并行思想和MPI编程模型对缓冲区算法的并行化实现和优化方法开展研究。实验结果显示，与ArcGIS Buffer工具相比，（1）当缓冲区结果多边形不合并时，虽然串行缓冲区算法的时间开销较高，但可轻易通过并行方式实现加速。（2）当缓冲区结果合并时，本文算法要明显优于ArcGIS Buffer工具，并且经过优化的并行缓冲区算法表现出了更高的计算效率和更大规模的数据处理能力。因此，基于几何部件缓冲区域合并的Buffer算法具备一定的实用价值，本文提出的按结点数量的任务分解方法和进程间结果&ldquo;树状&rdquo;归并策略是对缓冲区算法进行并行优化的有效途径，对GIS中其他矢量分析算法的并行化及相关优化工作也具有一定的借鉴意义。</p>

DOI

[Fan J F, Ma T, Zhou C H.et al.Buffer algorithm and parallel optimization method for the merging of geometric component buffer region[J]. Acta Geodaetica et Cartographica Sinica, 2014,43(9):969-975. ]

[33]
范俊甫,马廷,周成虎,等.基于集群MPI的图层级多边形并行合并算法[J].地球信息科学学报,2014,16(4):517-523.在集群环境下,基于MPI并行编程模型和OGC简单要素规范进行并行多边形合并时,需要处理叠加图层间要素的＂多对多＂映射关系,由于空间上相邻的多边形在要素序列上并不一定连续,导致无法按要素序列为子节点分配任务,给并行任务映射带来了困难。本文以集群环境下的并行多边形合并算法为研究对象,通过比较叠加分析中两种多边形映射关系对算法并行化带来的影响,基于R树空间索引、MySQL精确空间查询,以及MPI通信机制,提出了6种不同的并行任务映射策略;通过实验分析和比较了6种策略的优劣。结果显示：基于R树预筛选的直接合并策略,在各算法中具有最高的串行计算效率和优秀的并行性能表现。虽然MySQL精确空间查询的预筛选过程较为耗时,但可有效地过滤掉不真正相交的多边形,从而提高合并操作的效率。因此,在集群MPI环境下,基于R树和MySQL精确空间查询的预筛选策略是解决并行任务映射难题,实现图层级多边形并行合并算法的有效途径。

DOI

[Fan J F, Ma T, Zhou C H, et al.Implementation of cluster MPI-Based parallel polygon union algorithm at the feature layer level[J]. Journal of Geo-information Science, 2014,16(4):517-523. ]

[34]
Dowers S, Gittings B M, Mineter M J.Towards a framework for high-performance geocomputation: Handling vector-topology within a distributed service environment[J]. Computers, Environment and Urban Systems, 2000,24(5):471-486.This paper lays out a framework, based on the emerging Open GIS standards, which will allow the integration of parallel computing technology such that it becomes a viable component of a new generation of geographical information system (GIS) software. The significant costs of parallel re-implementation have thus far acted as a major disincentive to software vendors taking advantage of parallel technology to solve performance problems. These problems will be thrown into sharp focus by the demands of web-based geographical information services. Designs for a series of software libraries, which are subject to a prototype implementation involving the use of a sophisticated data format (Neutral Transfer Format Level 4), are examined with a view to re-implementation making use of the Open GIS Abstract Specification Model. A range of services are envisaged, which can provide functions at various levels from data retrieval, spatial analysis and map generation to specialist environmental models, which are made available over the Internet. Parallelism is seen as an important route for accelerating individual transactions. These services can equally be based on large specialised parallel servers or a co-operating set of under-used workstations. The implementation strategy involves insulating standard serial algorithms from parallelism through support libraries. These libraries handle, for example, the decomposition of the data, thus effectively encapsulating the parallelism within one component of the software and allowing the creation of high-performance software components which are compatible with the Open GIS service architecture.

DOI

[35]
Mineter M J.A software framework to create vector-topology in parallel GIS operations[J]. International Journal of Geographical Information Science, 2003,17(3):203-222.Parallel processing comprises the concurrent use of multiple processors to speed execution of one operation. Although techniques suited to most of the common geographical data models have been prototyped, the prominent exception has been vector-topology. This paper explores whether operations that create a vector-topological dataset can benefit from parallelisation. It describes techniques for using multiple processors concurrently to create vector-topology for multiple sub-areas, and for stitching these sub-areas together to form the resultant dataset. To achieve performance gains over sequential processing, the overhead of the stitching must be less than the gains from the parallel processing of sub-areas. These methods are tested in the context of the conversion of raster data to polygonal vector-topology. Speed-up in comparison to single-processor performance is achieved on both a 4-processor shared-memory Sun server and using up to 15 processors of a Cray T3E. The approach taken hides the parallelism and the management of the vector-topology in a software framework that simplifies the task of parallel application development.

DOI

[36]
Qin C Z, Zhan L J, ZHU A-X, et al.A strategy for raster-based geocomputation under different parallel computing platforms[J]. International Journal of Geographical Information Science, 2014,28(11):2127-2144.The demand for parallel geocomputation based on raster data is constantly increasing with the increase of the volume of raster data for applications and the complexity of geocomputation processing. The difficulty of parallel programming and the poor portability of parallel programs between different parallel computing platforms greatly limit the development and application of parallel raster-based geocomputation algorithms. A strategy that hides the parallel details from the developer of raster-based geocomputation algorithms provides a promising way towards solving this problem. However, existing parallel raster-based libraries cannot solve the problem of the poor portability of parallel programs. This paper presents such a strategy to overcome the poor portability, along with a set of parallel raster-based geocomputation operators (PaRGO) designed and implemented under this strategy. The developed operators are compatible with three popular types of parallel computing platforms: graphics processing unit supported by compute unified device architecture, Beowulf cluster supported by message passing interface (MPI), and symmetrical multiprocessing cluster supported by MPI and open multiprocessing, which make the details of the parallel programming and the parallel hardware architecture transparent to users. By using PaRGO in a style similar to sequential program coding, geocomputation developers can quickly develop parallel raster-based geocomputation algorithms compatible with three popular parallel computing platforms. Practical applications in implementing two algorithms for digital terrain analysis show the effectiveness of PaRGO.

DOI

[37]
Zhao C, Zhao Y, Meng L, et al.The key technological issues of parallel spatial database management system for parallel GIS[J]. Computer Knowledge & Technology, 2005,47(4):1265-1270.Abstract The technologies of organization and management of the massive volume spatial data are playing an important role in GIS. Especially, with the increasing of the volume of spatial data and the extending of the application of GIS, one of the requirements for the spatial database management systems (SDBMS) of the future is the ability to handle the huge volume spatial data. These applications involve spatial data mining and knowledge discovery, multi-dimensional and dynamic GIS, spatial-temporal GIS etc. Therefore, the paper presents a new software framework of spatial data management in GIS based on the parallel spatial database management system (PSDBMS) to solve the difficulties in storing and retrieval of the huge volume spatial data. The application of the parallel database management system in GIS will come forth lots of new issues. As we all know, the parallel GIS will provide a framework of high- performance computing for processing of the spatial data. In order to improving the integrated performance of parallel GIS, it is properly necessary to utilize the parallel database management system in the parallel GIS. The paper discusses the key technologic issues of the parallel spatial database management system, such as the software architecture of parallel GIS based on the PSDBMS, the technologies of the spatial data partitioning, and the related technologies of the optimal query in the PSDBMS etc. Due to the increasing requirements of GIS applications for high performance processing and storage of spatial data, we can foresee that the parallel GIS based on the PSDBMS should have the powerful ability to deal with the various complex applications in the future, and provide an effective software platform for processing, storage and retrieval of the spatial data.

[38]
陈达伦,陈荣国,谢炯.基于MPP架构的并行空间数据库原型系统的设计与实现[J].地球信息科学学报,2016,18(2):151-159.lt;p>快速高效地查询信息是衡量当前空间数据库性能的重要指标之一。传统的单节点关系型空间数据管理方式难以满足大数据量空间数据查询的需求,特别是高性能的复杂空间多表连接任务需求。鉴此,本文设计并实现了基于Massive Parallel Processing（MPP）架构的并行空间数据库中间件原型系统。系统充分利用无共享（shared-nothing）架构的优势,特别是针对空间数据的特性,设计了并行空间数据划分与导入、并行空间多表连接、空间数据查询优化等算法与模型。首先介绍了近年来并行数据库系统的发展现状,接着阐述了基于MPP架构的并行空间数据库中间件系统的查询计划算法及其系统架构,最后作者对一些大规模数据量做查询实验及其查询结果分析。实验表明,在处理挖掘大规模数据量时,该系统有近似线性的加速比,相比于传统单节点数据库,它能充分提高海量空间数据的复杂查询的性能,解决了空间数据库并行化处理海量数据的问题。</p>

DOI

[Chen D L, Chen R G, Xie J.Research of the parallel spatial database proto system based on MPP architecture[J]. Journal of Geo-information Science, 2016,18(2):151-159. ]

[39]
邱强. 并行矢量空间分析关键技术研究[D].北京:中国科学院大学,2015.

[Qiu Q.Research on key techniques of spatial analysis of parallel vector[D]. Beijing: University of Chinese Academy of Sciences, 2015. ]

[40]
Qiu Q, Yuan M, He F, et al. A parallel algorithm for line segment intersection[C]. Proceedings of the Geoinformatics (Geoinformatics), 2013 21st International Conference on, F, 2013. IEEE.

[41]
Qiu Q, Zhu X, Yao X, et al.A parallel strategy for plane sweep algorithm in multi-core system[C]. Proceedings of the International Geoscience and Remote Sensing Symposium, F, 2013.

[42]
邱强,方雷,姚晓,等.基于空间聚类的矢量空间数据并行计算划分方法[J].高技术通讯,2015(4):327-333.

[Qiu Q, Fang L, Yao X, et al.A spatial clustering based method for partitioning of vector spatial data for parallel computation[J]. Chinese High Technology Letters. 2015,4:327-333. ]

[43]
Zhao Y, Qiu Q, Fang J, et al. Fast parallel interpolation algorithm using CUDA[C]. Proceedings of the Geoscience and Remote Sensing Symposium, 2013 IEEE International, F, 2013. IEEE.

[44]
李峙,陈朝晖.空间叠加分析中的分而治之算法研究与应用[J].计算机工程与应用,2009,45(34):230-232.土地利用现状数据由CAD格式转换为GIS格式后需重新为图斑对象设置土地分类编码属性，为了提高海量空间数据情况下自动赋值的效率，研究了将分而治之算法应用于海量数据空间叠加分析以提高效率的方法。研究表明，对于所有需通过空间叠加分析来确定不同图层空间对象间的空间关系的问题，均可以采用分而治之方法来降低时间复杂度。在最小化分割的情况下，基于四叉树空间索引，分而治之算法可以使此类应用的时间复杂度降低为<EM>O</EM>（<EM>n</EM> lb <EM>n</EM>）。实际应用验证了该方法在海量空间数据处理中的效率和实用价值。

DOI

[Li Z, Chen Z H.Study and applications of divide and conquer algorithm in spatial overlay analysis[J]. Computer Engineering and Applications, 2009,45(34):230-232. ]

[45]
朱效民,潘景山,孙占全,等.基于OpenMP的两个地学基础空间分析算法的并行实现及优化[J].计算机科学,2013(2):8-11.

[Zhu X M, Pan J S, Sun Z Q, et al.Parallel implementation and optimization of two basic geo-spatial-analysis algorithms based on openMP[J]. Computer Science, 2013,2:8-11. ]

[46]
Eldawy A, Mokbel M F.A demonstration of spatialhadoop: An efficient mapreduce framework for spatial data[J]. Proceedings of the VLDB Endowment, 2013,6(12):1230-1233.This demo presents SpatialHadoop as the first full-fledged MapReduce framework with native support for spatial data. SpatialHadoop is a comprehensive extension to Hadoop that pushes spatial data inside the core functionality of Hadoop. SpatialHadoop runs existing Hadoop programs as is, yet, it achieves order(s) of magnitude better performance than Hadoop when dealing with spatial data. SpatialHadoop employs a simple spatial high level language, a two-level spatial index structure, basic spatial components built inside the MapReduce layer, and three basic spatial operations: range queries, k -NN queries, and spatial join. Other spatial operations can be similarly deployed in SpatialHadoop. We demonstrate a real system prototype of SpatialHadoop running on an Amazon EC2 cluster against two sets of real spatial data obtained from Tiger Files and OpenStreetMap with sizes 60GB and 300GB, respectively. <!-- #ads iframe { /* float: none;*/ width: 300px; border:0px !important; margin-top: 0px; margin-right: 12px; margin-bottom: 0px; margin-left: 0px; } #ads div { display: inline; width: 300px; } #ads .bsap_adhere { display:none; } BuySellAds Ad Code (function(){ var bsa = document.createElement('script'); bsa.type = 'text/javascript'; bsa.async = true; bsa.src = '//s3.buysellads.com/ac/bsa.js'; (document.getElementsByTagName('head')[0]||document.getElementsByTagName('body')[0]).appendChild(bsa); })(); End BuySellAds Ad Code Advertisements BuySellAds Zone Code End BuySellAds Zone Code BuySellAds Zone Code End BuySellAds Zone Code BuySellAds Zone Code End BuySellAds Zone Code

DOI

[47]
Eldawy A, Mokbel M F.SpatialHadoop: A MapReduce framework for spatial data[C]. Proceedings of the IEEE International Conference on Data Engineering, F, 2015.

[48]
Puri S, Agarwal D, He X, et al. MapReduce algorithms for GIS polygonal overlay processing[C]. Proceedings of the Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, F, 2013. IEEE.

[49]
Magalh ES, Svgam V A, Franklin W R, et al.Fast exact parallel map overlay using a two-level uniform grid[C]. Proceedings of the 4th International ACM Sigspatial Workshop on Analytics for Big Geospatial Data, 2015.

[50]
朱进,胡斌,邵华,等.基于内存数据库Redis 的轻量级矢量地理数据组织[J].地球信息科学学报,2014,16(1):165-172.矢量地理数据的高效组织管理是空间数据应用的关键问题之一。矢量地理数据服务作为一种重要的公众空间信息服务，已经得到广泛应用。公众对矢量地理数据服务性能提出了越来越高的要求，包括实时响应、高并发、高吞吐量等。当前的矢量地理数据服务后台数据存储组织，通常基于磁盘和关系数据库，其在面对公众日益增长的需求时已经显得力不从心。本文提出了一种以内存数据库Redis的轻量级矢量地理组织方法，能在高并发情况下有效提高矢量地理数据服务性能。论文首先分析了Redis的存储机制，设计了矢量地理数据库的分层组织模型，利用Redis丰富的数据结构对矢量地理数据及其相关元数据进行存储管理，然后，以网格索引为例，设计了Redis的空间索引，最后，设计Redis的矢量数据引擎原型系统，并进行了实验验证。结果表明，Redis的矢量地理数据库显著提高了响应速度，且并发性能更好，可广泛应用于大型空间数据库前端高速缓存和高性能空间索引库。

DOI

[Zhu J, Hu B, Shao H, et al.Research of lightweight vector geographic data management based on main memory database redis[J]. Journal of Geo-information Science, 2014,16(1):165-172. ]

[51]
张景云.基于Redis 的矢量数据组织研究[D].南京:南京师范大学,2013.

[Zhang J Y.Research on vector data organization based on Redis[D]. Nanjing: Nanjing Normal University, 2013. ]

[52]
Liu J, Li H, Gao Y, et al. A geohash-based index for spatial data management in distributed memory[C]. Proceedings of the Geoinformatics (GeoInformatics), 2014 22nd International Conference on, F, 2014. IEEE.

[53]

[54]
Zhao D, Gu Y, Huang Z.A new data-intensive parallel processing framework for spatial data[M]. Computer Engineering and Networking, Springer, 2014:375-83.

[55]
Zhang N, Zheng G, Chen H, et al.HBaseSpatial: A Scalable Spatial Data Storage Based on HBase[C]. Proceedings of the 2014 IEEE 13th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), F, 2014.

[56]
Yao X, Qiu Q, Zhang M, et al.Research on vector spatial data access based on Main memory database[C]. Proceedings of the Geoscience and Remote Sensing Symposium (IGARSS), 2015 IEEE International, F, 2015.

Options
文章导航

/

〈 〉