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

doi:10.3724/SP.J.1047.2017.01217

地球信息科学学报 ›› 2017, Vol. 19 ›› Issue (9): 1217-1227.doi: 10.3724/SP.J.1047.2017.01217

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

邱强¹(), 秦承志², 朱效民³, 赵晓芳¹, 方金云¹

1. 中国科学院计算技术研究所计算机应用研究中心, 北京 100190
2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京100101
3. 山东省计算中心,济南 250015

收稿日期:2017-05-12 修回日期:2017-08-11 出版日期:2017-10-09 发布日期:2017-10-09
作者简介:
作者简介：邱强(1987-),男,工程师,研究方向为地理信息系统并行计算及空间分析。E-mail: qiuqiang@ict.ac.cn
基金资助:
国家重点研发计划项目“全空间信息系统与智能设施管理”（2016YFB0502300）子课题“多粒度时空对象组织与管理”（2016YFB0502302）

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

QIU Qiang^1,^*(), QIN Chengzhi², ZHU Xiaomin³, ZHAO Xiaofang¹, FANG Jinyun¹

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

Received:2017-05-12 Revised:2017-08-11 Online:2017-10-09 Published:2017-10-09
Contact: QIU Qiang E-mail:qiuqiang@ict.ac.cn

摘要/Abstract

摘要：

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

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

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

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

QIU Qiang,QIN Chengzhi,ZHU Xiaomin,ZHAO Xiaofang,FANG Jinyun. Overview and Prospect on Spatial Analysis of Parallel Vectors in Pan-spatial Concept[J]. Journal of Geo-information Science, 2017, 19(9): 1217-1227.DOI:10.3724/SP.J.1047.2017.01217

图/表 5

图1

表1

表2

表3

图2

参考文献 25

[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. doi: 10.14778/2536222.2536227 pmid: 3814183
[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. doi: 10.1016/j.parco.2003.05.004
[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. doi: 10.13485/j.cnki.11-2089.2014.0122
	[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. ] doi: 10.13485/j.cnki.11-2089.2014.0122
[33]	范俊甫,马廷,周成虎,等.基于集群MPI的图层级多边形并行合并算法[J].地球信息科学学报,2014,16(4):517-523. doi: 10.3724/SP.J.1047.2014.00517
	[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. ] doi: 10.3724/SP.J.1047.2014.00517
[1]	周成虎. 全空间地理信息系统展望[J].地理科学进展,2015,34(2):129-131. doi: 10.11820/dlkxjz.2015.02.001
	[Zhou C H.Prospects on pan-spatial information system[J]. Progress in Geography, 2015,34(2):129-31. ] doi: 10.11820/dlkxjz.2015.02.001
[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. doi: 10.1016/S0198-9715(00)00011-9
[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. doi: 10.1080/13658810210149443
[2]	华一新. 全空间信息系统的核心问题和关键技术[J].测绘科学技术学报,2016,33(4): 331-335. doi: 10.3969/j.issn.1673-6338.2016.04.001
	[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. ] doi: 10.3969/j.issn.1673-6338.2016.04.001
[3]	Shekhar S, Xiong H.Encyclopedia of GIS[M]. Berlin: Springer, 2008.
[4]	张晓祥. 大数据时代的空间分析[J].武汉大学学报·信息科学版,2014,39(6):655-659.
[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. doi: 10.1080/13658816.2014.911300
[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.
[38]	陈达伦,陈荣国,谢炯.基于MPP架构的并行空间数据库原型系统的设计与实现[J].地球信息科学学报,2016,18(2):151-159. doi: 10.3724/SP.J.1047.2016.00151
	[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. ] doi: 10.3724/SP.J.1047.2016.00151
[4]	[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: 10.3969/j.issn.1673-5692.2013.01.002
[39]	邱强. 并行矢量空间分析关键技术研究[D].北京:中国科学院大学,2015.
	[Qiu Q.Research on key techniques of spatial analysis of parallel vector[D]. Beijing: University of Chinese Academy of Sciences, 2015. ]
[5]	[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. ] doi: 10.3969/j.issn.1673-5692.2013.01.002
[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.
[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.
[7]
[8]	张林波. 并行计算导论[M].北京:清华大学出版社,2006.
[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. ]
[8]	[Zhang L B.Introduction to parallel computing[M]. Beijing: Tsinghua University press, 2006. ]
[9]	迟学斌.高性能并行计算[M].2005. https://wenku.baidu.com/view/ 52aa1ba8bb4cf7ec4bfed003. html.
[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. doi: 10.3778/j.issn.1002-8331.2009.34.072
[9]	[Chi X B, High performance parallel computing[M].2005. https://wenku.baidu.com/view/52aa1ba8bb4cf7ec4bfed003.html
[10]	李德仁,王树良,李德毅.空间数据挖掘理论与应用[M].北京:科学出版社,2006.
[44]	[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. ] doi: 10.3778/j.issn.1002-8331.2009.34.072
[45]	朱效民,潘景山,孙占全,等.基于OpenMP的两个地学基础空间分析算法的并行实现及优化[J].计算机科学,2013(2):8-11.
[10]	[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.
[45]	[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. doi: 10.14778/2536274.2536283
[12]	Bentley J L, Ottmann T A.Algorithms for reporting and counting geometric intersections[J]. Computers, IEEE Transactions on, 1979,100(9):643-647. doi: 10.1109/TC.1979.1675432
[13]	Nievergelt J, Preparata F P.Plane-sweep algorithms for intersecting geometric figures[J]. Communications of the ACM, 1982,25(10):739-47. doi: 10.1145/358656.358681
[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.
[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. doi: 10.1145/147508.147511
[15]	Balabran I J. An optimal algorithm for finding segments intersections[C].Proceedings of the eleventh annual symposium on Computational geometry,F, 1995,ACM.
[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. doi: 10.3724/SP.J.1047.2014.00165
[16]	毛定山. 基于计算几何的矢量数据叠加分析算法研究[D].济南:山东科技大学,2007.
	[Mao D S.Research on vector data overlay analysis algorithm based on computational geometry[D]. Jinan: Shandong Technolgy Univeristy, 2007. ]
[50]	[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. ] doi: 10.3724/SP.J.1047.2014.00165
[51]	张景云.基于Redis 的矢量数据组织研究[D].南京:南京师范大学,2013.
[17]	张文艺. GIS 缓冲区和叠加分析[D].长沙:中南大学, 2007.
	[Zhang W Y.GIS buffer and overlay analysis[D]. Changsha: Central South University, 2007. ]
[51]	[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.
[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. ]
[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.
[19]	朱效民,赵红超,刘焱,等.矢量地图叠加分析算法研究[J].中国图象图形学报,2010,15(11):1696-706. doi: 10.11834/jig.20101119
	[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. ] doi: 10.11834/jig.20101119
[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.
[20]	朱效民,赵红超,方金云.鲁棒高效的矢量地图叠加分析算法[J].遥感学报,2012,16(3):448-465. doi: 10.11834/jrs.20120123
	[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. ] doi: 10.11834/jrs.20120123
[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. doi: 10.1016/j.parco.2003.07.001
[23]	吴立新,杨宜舟,秦承志,等.面向新型硬件构架的新一代 GIS 基础并行算法研究[J].地理与地理信息科学,2013,29(4):1-8. doi: 10.7702/dlydlxxkx20130401
	[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. ] doi: 10.7702/dlydlxxkx20130401
[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.

研究方向		代表性研究	研究成果
空间数据并行处理		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数据库平台

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

	内存数据库	矢量空间分析算法I/O
读写性能	数据常驻内存,读写速度快的key-value数据结构	数据密集特征,I/O时间成为制约算法效率的性能瓶颈
存储容量	存储容量存在上限,超过内存限制会大量使用swap,降低性能	以矢量数据为存储模型,表达空间对象信息丰富,但数据规模较小
持久化	安全稳定的持久化策略	对空间数据存储和系统容错有较高要求
Master-Slave复制	适合集群应用环境	在集群环境中,通过并行计算技术提高算法效率

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

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

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 25

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	曾梦熊, 华一新, 张江水, 曹一冰, 张政. 多粒度时空对象动态行为表达模型与方法研究[J]. 地球信息科学学报, 2021, 23(1): 104-112.
[2]	李锐, 石佳豪, 董广胜, 刘朝辉. 多粒度时空对象组成结构表达研究[J]. 地球信息科学学报, 2021, 23(1): 113-123.
[3]	张正方, 闫振军, 王增杰, 傅蓉, 罗文, 俞肇元. 基于Bayes网络的多粒度时空对象地理过程演化建模——以新安江模型为例[J]. 地球信息科学学报, 2021, 23(1): 124-133.
[4]	陈文静, 李锐, 董广胜, 李江. 网络地理信息服务中用户空间访问聚集行为研究[J]. 地球信息科学学报, 2021, 23(1): 93-103.
[5]	谢雨芮, 江南, 赵文双, 郝睿. 基于多粒度时空对象的作战实体对象化建模研究[J]. 地球信息科学学报, 2021, 23(1): 84-92.
[6]	张政, 华一新, 张亚军, 曾梦熊, 杨振凯. 以节点为中心的关系边聚类与可视化算法[J]. 地球信息科学学报, 2020, 22(9): 1779-1788.
[7]	林珲, 胡明远, 陈旻, 张帆, 游兰, 陈宇婷. 从地理信息系统到虚拟地理环境的认知转变[J]. 地球信息科学学报, 2020, 22(4): 662-672.
[8]	秦承志. 数字地形分析方法研究的维度——精准、高效、易用[J]. 地球信息科学学报, 2020, 22(4): 720-730.
[9]	邓敏, 蔡建南, 杨文涛, 唐建波, 杨学习, 刘启亮, 石岩. 多模态地理大数据时空分析方法[J]. 地球信息科学学报, 2020, 22(1): 41-56.
[10]	王浩, 王含宇, 杨名宇, 许永森. Retinex图像增强在GPU平台上的实现[J]. 地球信息科学学报, 2019, 21(4): 623-629.
[11]	潘淼鑫, 林甲祥, 陈崇成, 叶晓燕. 基于C-SOM和Spark的并行空间离群挖掘方法及应用[J]. 地球信息科学学报, 2019, 21(1): 128-136.
[12]	孙经纬, 孙广中, 詹石岩, 毛睿, 周英华. SA*：一种多线程路径规划算法[J]. 地球信息科学学报, 2018, 20(6): 753-761.
[13]	华一新, 周成虎. 面向全空间信息系统的多粒度时空对象数据模型描述框架[J]. 地球信息科学学报, 2017, 19(9): 1142-1149.
[14]	江南, 方成, 陈敏颉. 全空间信息系统认知与表达初探[J]. 地球信息科学学报, 2017, 19(9): 1150-1157.
[15]	张政, 华一新, 张晓楠, 郭邵萌, 文娜. 多粒度时空对象关联关系基本问题初探[J]. 地球信息科学学报, 2017, 19(9): 1158-1163.