面向新型硬件构架的新一代GIS基础并行算法研究

2013-08-08吴立新杨宜舟秦承志张树清张立强方金云孙文彬刘善军

地理与地理信息科学 2013年4期

吴立新，杨宜舟，秦承志，张树清，张立强，方金云，孙文彬，刘善军

（1.东北大学测绘遥感与数字矿山研究所，辽宁沈阳 110819；2.中国矿业大学物联网（感知矿山）中心，江苏徐州 221008；3.北京师范大学民政部／教育部减灾与应急管理研究院，北京 100875；4.中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室，北京 100101；5.中国科学院东北地理与农业生态研究所，吉林长春 130102；6.北京师范大学遥感科学国家重点实验室，北京 100875；7.中国科学院计算技术研究所，北京 100190；8.中国矿业大学（北京）地球科学与测绘工程学院，北京 100083）

0 引言

自20世纪60年代早期罗杰·汤姆林森博士提出地理信息系统（Geographic Information System，GIS）概念［1］以来，经过几代人共同努力，GIS由工具到系统、再到科学［2］，其发展非常迅速。特别是计算机技术的高速发展已成为推动GIS技术进步的主要动力，几乎每一次计算机技术的重要进展都带动GIS的重大进步，如空间数据的管理、网络GIS、三维GIS等［3］。近年来，以计算机软硬件为基础的Internet技术和并行计算技术迅速发展，尤其以并行计算为核心的云计算技术得到越来越多应用。硬件能力的发展特征为：CPU的单核主频提高有限，而核数却不断增加，CPU向着更宽（核数更多）的方向发展。与此同时，地理空间数据采集技术随着对地观测技术的发展而不断改进，人类获取空间数据的效率和数据量更是飞速增长，GIS面临的空间数据和地理计算问题更加复杂和多样化，GIS处理数据的量和空间分析的规模越来越大［4］，现有GIS软件并不能满足减灾应急、流域模拟、智能交通、宏观规划、区域发展等大型求解需求。

分析GIS的基本原理与算法现状［5］可以发现：当前主流GIS软件如ArcGIS、SuperMap、MapGIS、GeoStar等均是基于单机单核的硬件构架而设计的，其中ArcGIS online、SuperMap云虽提供了云模式，但主要侧重于数据共享服务。现有GIS软件在单进程（单机单核）环境下对计算资源的利用已达极致，不能发挥当前主流硬件架构的众核（多核与集群）并行优势，形成了GIS计算能力与硬件资源能力的巨大反差以及GIS软件能力与复杂地理计算需求的巨大鸿沟。如2011年日本3.11大地震后，我们曾利用ArcGIS、90mDEM和实测浪高数据来插值计算日本东海岸的海啸淹没情形，发现ArcGIS运行崩溃、无法完成任务。因此，充分利用新型硬件构架所提供的强大计算资源，研究基础地理并行算法、开发新一代高性能GIS，已成为当务之急和必须迈进的GIS发展新阶段。

1 研究背景

早在1991年，Richard和Steve领导的研究小组即开始了面向应用的GIS并行计算模型和并行算法研究［6］。但是，受当时并行计算机硬件和并行计算技术的限制，并行GIS在很长一段时间未能取得突破性进展。直到近年，随着并行计算理论与方法的成熟及并行计算机的普及，并行GIS研究才重新成为空间信息领域的研究热点。Nathan［7］研究提出了两种面向服务的并行GIS模式：一种是采用基于Google的MapReduce开源框架Hadoop而构建的HadoopGIS；另一种是基于 MPI构建的Cluster－GIS。但是，这些框架都是基于web的，严重受限于网络连接的状况、并行计算服务的队列状况以及大规模计算设施上并行计算服务的吞吐量［8］，没有开发真正意义上的基础地理并行算法，难以执行大规模复杂地理计算任务。

鉴于GIS的技术现状和国际发展趋势，“十二五”开局伊始，我国科技部863对地观测与导航领域重点规划和优先启动了国内首个基于新型硬件体系架构、面向大规模复杂地理计算的高性能并行GIS研发项目，旨在突破GIS并行计算算法库与中间件，开发出完全自主知识产权的新一代高性能GIS——“High－Performance Geographic Information System（HiGIS）”。该项目分设了地理计算引擎与开放式地理计算构建环境、地理数据转换和可视化并行技术与中间件、地理空间计算并行算法与中间件、数字地形分析并行技术与中间件、智能地理计算并行技术与中间件、空间统计与过程模拟并行计算共6个课题，由东北大学、中科院地理科学与资源研究所、中科院计算技术研究所、中科院东北地理与农业生态研究所和北京师范大学联合承担了其中的基础算法课题——地理空间计算并行算法与中间件。该课题的任务是基于当前多核处理器和并行集群这一新型硬件架构及并行软件开发环境，针对矢量和栅格两类基础地理计算算法的特点，对现有地理空间计算串行算法库进行并行化改造、并行优化和设计新的并行算法，发挥多核、并行集群计算环境的能力和优势，提高GIS算法效率，提升基础地理空间计算性能，为HiGIS及其他高性能地理计算平台的搭建提供开放的核心算法库，为下一代并行GIS的应用服务奠定核心计算技术支撑。

2 基础并行算法研究现状分析

数据与数据结构是GIS的基础和核心。矢量和栅格作为GIS最基础的两类空间数据结构，各具优势且互为补充，其发展并行不悖。现已逐步形成了较为完善的基于矢量和栅格的GIS串行算法库，为各类基础GIS软件与应用提供了支撑。分析与地理空间计算相关的文献、调研国际主流GIS软件的功能架构，可按空间分析功能将基于矢量的GIS基础计算划分为空间索引构建与数据检索、空间关系计算与查询分析、缓冲区构建与分析、叠加计算与分析、网络分析等5大类约50余种算法；将基于栅格的GIS基础计算划分为栅格属性变换、窗口分析、连通性分析、追踪分析、聚合分析、叠加分析、聚类分析、模糊聚类分析、判别分析、主成分分析、数学形态学分析、滤波分析等12大类约30余种算法。下面分述其研究现状。

2.1 矢量并行算法

矢量地理计算算法并行化研究已有20年历史，但仅限于简单的空间分析算法，如最短路径分析、叠加分析等，关于复杂的空间关系并行算法如网络分析并行算法的研究进展鲜有报道。表1按算法功能对当前GIS矢量并行算法研究现状进行概括。

表1 矢量数据基础地理并行算法研究现状Table 1 Research status of vector－based geographic parallel algorithms

2.2 栅格并行算法

栅格地理计算算法并行化研究在国内外早有开展，但多针对单一算法的并行化。Li等实现了用于支撑元胞自动机的栅格地理计算算法库［37］；Guan等基于MPI构建了较为通用的栅格地理计算并行算法编程工具库［38］，并应用于元胞自动机模拟，为设计开发更加基础的并行算子库做出了探索性工作。当前对地理空间计算算法工具的相关研究还未达到可用的算法库级别。表2按算法功能概括了当前GIS栅格算法的并行化研究现状。

表2 栅格数据基础地理算法研究现状Table 2 Research status of raster－based geographic parallel algorithms

2.3 现状总体特点

1）当前商业GIS软件（如ArcGIS online［62］、SuperMap云［63］）主要是针对数据的共享与服务，未提供在新型硬件构架下的空间分析并行计算功能或算法库；2）Richard提供的MIMD算法库已不适用于当前的硬件构架，美国新兴的CyberGIS也仅针对现有计算资源的共享服务，而非从基础上设计普适的基础并行算法库；3）现有并行算法未形成统一的接口标准，不能形成一个有效系统服务于实际；4）现有并行算法多为算法级别的并行，扩展性不强，需设计开发更加基础的并行算子库；5）现有并行算法的鲁棒性不强，稳健性与效率得不到有效保障；6）现有并行算法的适应性不强，仅能在某一固定的并行环境下运行，需开发出适用于多种并行环境的普适性并行算法。

3 基础地理算法特点分析

基础地理算法虽然功能各异，但其计算特点可概括为4种基本特征：1）本地计算，即每一目标单元的计算结果只与其本身、或者相关图层中与其具有相同空间位置的目标单元有关，与其它目标单元无关；2）邻域计算，即每个目标单元的计算结果与指定范围内的相邻目标单元有关；3）区域计算，即单个目标单元的计算结果与满足某种条件的一定空间范围内的目标单元有关，不同目标单元在计算时所涉及的空间范围不同；4）全局计算，即单个目标单元的计算结果与所有目标单元有关。这些不同的计算特点将直接影响到相应类型算法的并行化设计与实现。课题组对基础地理算法类别及其计算特点进行了系统的分析总结，概括如表3所示，其中某一功能算法类中可能包含不同的计算特征（尤其是对一些改进型的算法），如栅格属性变换中的栅格属性函数变换算法属于本地计算，而直方图均衡化算法属于全局计算。

4 基础地理并行算法开发策略

分析可知：在各种基础地理计算算法中，已有部分算法（尤其是栅格算法）实现了并行化，可对这些算法进行优化提质；对于大多数基础地理空间计算算法（尤其是基于矢量的各类空间分析算法），其并行化技术相对复杂。对于这类算法，通过分析其串行化算法的计算流程与具体特点，进而确定其计算流程的子环节是否具备可直接并行化特征。对于子过程可直接并行化的算法，需进一步分析其子过程的并行特点，按照数据密集型、计算密集型、I／O密集型特征（表4）对并行算法进行详细设计；对于子过程不易直接并行化的算法，则需要根据串行算法的基本原理进行改进，或创新设计出间接的并行算法。

表3 基础地理计算算法特点分析Table 3 The algorithm characteristics for the basic geographic computing

结合复杂地理计算与HiGIS对基础地理空间计算的功能需求，在保证地理空间计算与分析功能覆盖面足够的前提下，课题组研究提出了基础地理空间并行算法开发与算法库建设的总体策略（图1）。同时，针对具体算法的计算特点及所采用的并行策略，

表4 地理计算算法并行策略的简要归纳Table 4 Brief summary on parallelism strategy for geographic computing algorithms

还需对具体算法中各个子过程的并行性进行细化分析。课题组分析提出了各类地理计算串行算法的计算流程、特点及可并行化性，归纳并提出其中通用的、执行频率高、计算代价大的计算步骤，进而设计可直接应用于地理计算算法实现的并行算子（图2）。

图1 基础地理计算并行算法库设计与开发策略Fig.1 The strategy for design and development of basic geographic parallel algorithms library

图2 基于并行算子实现并行算法Fig.2 Implementation of parallel algorithms based on the parallel operators

5 基础地理并行算法开发进展

首先，使用程序语言及成熟的并行编程工具（如MPI、OpenMP、CUDA等）进行编程，实现并行算法。同时，建立面向不同应用的地理测试数据集（包含各种类型的矢量、栅格数据），并按照不同应用目标和领域进行分组，每组包含的数据量从较小至大规模（矢量数据集最大包含6 000万个对象、栅格数据集最大为10GB），数据计算的复杂程度从简单至复杂。然后，全面测试和分析所开发的并行算法的性能和鲁棒性，通过指定并行计算参数，对测试数据集中的数据进行计算，对计算过程中出现的运行时间、占用空间、计算效率等指标进行记录和分析，进而反馈检查和修改并行算法。

在此基础上，针对总项目设计的跨硬件平台开发环境，再将基础级中间件进行二次封装，形成可以在各种计算平台上运行的通用接口级中间件。中间件实现完毕后将其部署在不同硬件平台（单机单路多核、单机多路多核、多机多路多核等）、不同操作系统（Windows、Linux、Unix等）的高性能计算设备上，全面测试中间件的可用性、稳定性、跨平台性，并不断完善。

按照项目总体部署和课题任务安排，在课题组内部统一协调、强化管理和扎实推进下，在全体研发人员的不断攻坚克难、交流学习和共同努力下，对空间索引、空间关系、缓冲区分析、叠加分析、网络分析、矢量数据处理等44种矢量典型算法，连通性分析、叠加分析、聚类分析、数学形态学、聚合分析、模糊聚类分析、主成分分析等26种栅格典型算法进行了研究。目前，已完成了约70余种算法的详细设计及编程实现，其中约有50余种算法［63－93］已在单机多核、多机多核及项目组的高性能集群上测试及进行集成应用，包括一些创新性较强的基础并行算法（表5）。这些算法已在项目环境中形成可用、稳定和高效的中间件，这些中间件已作为基础工具库支持了复杂地理计算的应用示范。

表5 基础地理并行算法的典型创新Table 5 Main innovations on basic geographic parallel algorithms

6 结论与展望

本课题在863计划项目“面向新型硬件架构的复杂地理计算平台”的总体部署下（包括环境搭建、数据处理、并行计算、地形分析、流域模拟、可视化等），在新一代高性能GIS平台——HiGIS开发的统一要求下，针对复杂地理计算需求、面向多核处理器与并行集群的新型硬件架构，基于现行主流的编程技术，从数据划分、算子归纳、并行算法着手，开发实现了稳定可用的基础算法库与中间件。本课题与“地理数据转换与可视化并行技术与中间件”课题的研究成果，将共同形成基础地理空间计算并行中间件，直接服务于时空数据分析与复杂地理计算模拟，为“数字地形分析并行技术与中间件”课题及“智能地理计算并行技术与中间件”课题提供核心算法库，为HiGIS提供基础技术与算法支撑。Hi－GIS将不仅提供高端的计算中心与数据中心相结合的服务模式，还将提供普及型的C／S和B／S服务模式，不同层次、不同领域的用户可以根据自己的应用需求和计算特点，灵活、便捷地搭建基于中间件的应用系统和享受HiGIS的计算服务。相信在科技部国家遥感中心大力支持下，在项目组和领域专家的统一协调下，在各课题成员的共同努力下，HiGIS将发展成为新一代GIS之骄子，促进我国GIS研究、技术、系统和应用的跨越式发展，并产生重要的国际影响。

然而，面向新型硬件构架的HiGIS仍然面临以下挑战性问题，需要不断改进和完善：1）海量多源异构空间数据的存储、管理仍是基于传统的数据库系统（如Oracle Spatial、MySQL、PostGIS等），未来它应具备支持数字地球（区域、全球）和全球空间格网数据的时空统一组织、管理与更新服务能力；2）并行算法库对多维时空数据的处理能力还较薄弱，未来应采用新的时空思维设计新的数据结构与新的计算模式，实现更为强大的时空数据处理与分析表达能力；3）空间模型与物理模型的耦合程度还很低，未来应面向灾害应急、全球变化与地球系统科学研究等大规模、动态过程的复杂系统问题，设计相应的物理建模环境与参数同化技术，支持中、大和超大尺度的地球系统科学模拟分析与应用。

［1］ TOMLINSON R F.Thinking about GIS：Geographic Information Systems Planning for Managers［M］.Redlands，CA：ESRI Press，2003.

［2］ GOODCHILD M F.Geographical information science［J］.International Journal of Geographical Information Systems，1992，6：31－46.

［3］龚健雅.当代地理信息系统进展综述［J］.测绘与空间地理信息，2004，27（1）：5－11.

［4］方裕，周成虎，景贵飞，等.第四代GIS软件研究［J］.中国图形图象学报，2001，6（9）：817－822.

［5］吴立新，史文中.地理信息系统原理与算法［M］.北京：科学出版社，2003.

［6］ HEALEY R，DOWERS S，GITTINGS B，et al.Parallel Processing Algorithms for GIS［M］.Taylor＆Trancis，1998.

［7］ NATHAN T K.Alternative Approaches to Parallel GIS Processing［D］.Arizona State University，2009.

［8］ TAN Y，GU X，WANG H.Adaptive system anomaly prediction for large－scale hosting infrastructures［A］.Proceeding of PODC［C］.Zurich，Switzerland，2010.

［9］ KARNEL I，FALOU TSOS C.Parallel R－trees［C］.USA：ACM SIGMOD，1992.

［10］ BANG K S，LU H Z.The PML－tree：An efficient parallel spatial index structure for spatial databases［A］.Proceedings of the 1996ACM 24th Annual Conference on Computer Science［C］.1996.

［11］ SCNNITZER B，LEUTENEGGER S T.Master－client R－tree：A new parallel R－tree architecture［A］.Proc.SSDBM Conf［C］.1999.68－77.

［12］ FU X D，WANG D X，ZHENG W M.GPR－tree：A global parallel index structure for multiattribute declustering on cluster of workstations［A］.Proceedings of the 1997Advances in Parallel and Distributed Computing Conference［C］.1997.

［13］于波，郝忠孝.基于DPR树的分布式并行空间索引［J］.计算机技术与发展，2010，20（6）：39－42.

［14］ WANG B T，HORINOKUCHI H，KANEKO K，et al.Parallel R－tree search algorithm on DSVM［A］.Proceedings of the Sixth International Conference on Database Systems for Advanced Applications［C］.1999.237－245.

［15］ LAI S H，ZHU F H，SUN Y Q.A design of parallel R－tree on cluster of workstations，databases in networked information systems［A］.Lecture Notes in Computer Science［C］.2000，1966／2000：119－133.

［16］ KYOUNGSOO B，SEO D M，SONG S，et al.An index structure for parallel processing of multidimensional data，advances in Web－age information management［A］.Lecture Notes in Computer Science［C］.2005，3739／2005：589－600.

［17］赵园春，李成名，赵春宇.基于R树的分布式并行空间索引机制研究［J］.地理与地理信息科学，2007，23（6）：38－41.

［18］ EGENHOFER M.Reasoning about binary topological relations［A］.GUNTHER O，SCHEK H J.Lecture Notes in Computer Science［C］.Second Symposium on Large Spatial Databases，Zurich，Switzerland，1991，525：143－160.

［19］ RANDELL D A，CUI Z，COHN A G.Spatial logic based on regions and connection［A］.Proc.3rd Int.Conf.on Knowledge Representation and Reasoning［C］.Morgan Kaufmann，San Mateo，1992.165－176.

［20］ FRANK A U.Qualitative spatial reasoning：Cardinal directions as an example［J］.International Journal of GIS，1996，10（3）：269－290.

［21］刘亚彬，刘大有.空间推理与地理信息系统综述［J］.软件学报，2000，11（12）：1598－1606.

［22］ WILSON G V.Assessing the usability of parallel programming systems：The cowichan problems［A］.Proceedings of the IFIP Working Conference on Programming Environments for Massively Parallel Distributed Systems［C］.1994.183－193.

［23］ LANGENDOEN H F.Parallelizing the Polygon Overlay Problem Using Orca［D］.Vrije Universiteit Amsterdam，1995.

［24］ THEOHARIS，IAN PAGE.Two parallel methods for polygon clipping［J］.Computer Graphics Forum，1989，8（2）：107－114.

［25］ MOHAMMAD Q，AZZAM S，ALMOBAIDEEN W.Parallel implementation of polygon clipping using transputer［J］.American Journal of Applied Sciences，2009，6（2）：214－218.

［26］姚艺强，高劲松，孟令奎，等.网格环境下缓冲区分析的并行计算［J］.地理空间信息，2007，5（1）：98－101.

［27］ PANG L，LI G Q，YAN Y X.Research on parallel buffer analysis based on grided based HPC［A］.International Geoscience and Remote Sensing Symposium，IGARSS 2009［C］.2009.200－203，327－332.

［28］ KALOANAR R，THAMBAIDURAI P.Optimizing shortest path queries with parallelized arc flags［A］.The Proceedings of IEEE International Conference on Recent Trends in Information Technology［C］.2011.1－6.

［29］ DANIL D，BASTIAN K.THOMAS P.Parallel computation of best connections in public transportation networks［A］.24th International Parallel and Distributed Processing Symposium［C］.IEEE Computer Society，2010.1－12.

［30］ LAUTHER U.An extremely fast，exact algorithm for finding shortest paths in static networks with geographical background［C］.GI－Tage，2004，22：219－230.

［31］ GARCIA L F，MELIAN B B，MORENO P J A，et al.Parallelization of the scatter search for the p－median problem［J］.Parallel Computing，2003，29（5）：575－589.

［32］ DABROWSHI J.Parallelization techniques for tabu search［J］.Lecture Notes in Computer Science，2007，4699：1126－1135.

［33］ FESTA P，RESECNDE M G C.Hybridizations of GRASP with Path－Relinking［R］.AT＆T Labs Research，2011.1－19.

［34］ XIAO N.A parallel cooperative hybridization approach to the p－median problem［J］.Environment and Planning B：Planning and Design，2012，39（4）：755－774.

［35］ CORDEAU J F，MAISCHBERGER M.A parallel iterated tabu search heuristic for vehicle routing problems［J］.Computers＆ Operations Research，2011，39（9）：2033－2050.

［36］ GROER C，GOLDEN B，WASIL E.A parallel algorithm for the vehicle routing problem［J］.INFORMS Journal on Computing，2011，23（2）：315－330.

［37］ LI X，ZHANG X，YEH A，et al.Parallel cellular automata for large－scale urban simulation using load－balancing techniques［J］.International Journal of Geographical Information Science，2010，24（6）：803－820.

［38］ GUAN Q，CLARKE K C.A general－purpose parallel raster processing programming library test application using ageographic cellular automata model［J］.International Journal of Geographical Information Science，2010，24（5）：695－722.

［39］ BADER D A，JAJA J.Parallel algorithm for image histogramming and connected components with an experimental study［J］.Parallel and Distributed Computing，1996，35（2）：123－133.

［40］卢丽君，廖明生，张路.分布式并行计算技术在遥感数据处理中的应用［J］.测绘信息与工程，2005，30（3）：1－3.

［41］张健，徐茂兴.连通域标记并行算法在多核处理器上的设计和实现［J］.计算机系统应用，2010（4）：140－143.

［42］ MOWER J E.Data－parallel procedures for drainage basin analysis［J］.Computers ＆ Geosciences，1994，20（9）：1365－1378.

［43］ O′CALLAGHAN J F，MARK D M.The extraction of drainage networks from digital elevation data［J］.Computer Vision，Graphics，and Image Processing，1984，28（3）：323－344.

［44］ GONG J，XIE J.Extraction of drainage networks from large terrain datasets using high throughput computing［J］.Computers ＆ Geosciences，2009，35（2）：337－346.

［45］ ORTEGA L，RUEDA A.Parallel drainage network computation on CUDA［J］.Computers ＆ Geosciences，2010，36（2）：171－178.

［46］方金云，何建邦.并行栅格数据处理网格服务节点软件的关键技术［J］.地球信息科学，2004，6（1）：17－21.

［47］周海芳.遥感图像并行处理算法的研究与应用［D］.国防科技大学，2003.

［48］蒋艳凰.遥感图像高精度并行监督分类技术研究［D］.国防科技大学，2004.

［49］ RAJASEKARAN S.Efficient parallel hierarchical clustering algorithms［J］.Parallel Distrib.Syst.，2005，16（6）：497－502.

［50］ DASH M，PETRUTIU S，SCHEUERMANN P.POP：Fast yet accurate parallel hierarchical clustering using partitioning［J］.Data ＆ Knowledge Engineering，2007，61（3）：563－578.

［51］ STOFFEL K，BELKONIENE A.Parallel k／h－means clustering for large data sets［A］.AMESTOY P.Euro－Par′99Parallel Processing：5th International Euro－Par Conference［C］.1999.1451－1454.

［52］ DHILLON I，MODHA D.A data－clustering algorithm on distributed memory multiprocessors［A］.ZAKI M J，HO C.Large－Scale Parallel Data Mining［C］.2000.245－260.

［53］ NAGESH H，GOIL S，CHOUDHARY A.Parallel algorithms for clustering high－dimensional large－scale datasets［A］.GROSSMAN R L，KAMATH C，KEGELMEYER P，et al.Data Mining for Scientific and Engineering Applications［C］.2001.335－356.

［54］ KWOK T，SMITH K，LOZANO S，et al.Parallel fuzzy cmeans clustering for large data sets［A］.MONIEN B，FELDMANN R.Euro－Par 2002Parallel Processing：8th International Euro－Par Conference［C］.2002.27－58.

［55］ MODENESI M，COSTA M，EVSUKOFF A，et al.Parallel fuzzy cmeans cluster analysis［A］.DAYDÉ M，PALMA J M L M，COUTINHOÁL G A，et al.High Performance Computing for Computational Science－VECPAR 2006［C］.2007.52－65.

［56］ MODENESI M，EVSUKOFF A，COSTA M.A load balancing Knapsack algorithm for parallel fuzzy c－means cluster analysis［A］.PALMA J M L M，AMESTOY P R，DAYDÉ M，et al.High Performance Computing for Computational Science——VECPAR［C］.2008.269－279.

［57］ HAWICK K A，CODDINGTON P D，JAMES H A.Distribu－ted frameworks and parallel algorithms for processing largescale geographic data［J］.Parallel Computing，2003，29（10）：1297－1333.

［58］胡冰，周海芳，王攀峰，等.遥感图像PCA并行算法研究与实现［J］.微电子学与计算机，2006，23（10）：153－161.

［59］ ANDRECUT M.Parallel GPU implementation of iterative PCA algorithms［J］.Computational Biology，2009，16（11）：1593－1599.

［60］ BOUKERRAM A，AZZOU S A.Parallelisation of algorithms of mathematical morphology［J］.Computer Science，2006，2（8）：615－618.

［61］刘冬.数学形态学与变换域图像去噪算法及其并行化研究［D］.吉林大学，2011.

［62］ http：／／www.esri.com／software／arcgis／arcgisonline／features.2012－12－31.

［63］ http：／／www.supermap.com.cn／html／sofewarebig＿3.html.2012－12－31.

［64］ ZHANG L Q，HAN C M，ZHANG L，et al.Web－based visualization of large 3Durban building models［J］.International Journal of Digital Earth，2012.1－15（doi：10.1080／17538947.2012.667159）.

［65］ ZHANG M，ZHANG L Q，MATHIOPOULOS P T，et al.A geometry and texture coupled flexible generalization of urban building models［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2012，70：1－14.

［66］ ZHANG L Q，REN Y C，SHI H L，et al.Modeling and analyzing 3Dcomplex building interiors for effective evacuation simulations［J］.Fire Safety，2012，53：1－12.

［67］ QIN C Z，ZHAN L J.Parallelizing flow－accumulation calculations on graphics processing units—From iterative DEM preprocessing algorithm to recursive multiple－flow－direction algorithm［J］.Computers ＆ Geosciences，2012，43：7－16.

［68］ CHEN C，LIU CY，ZHANG S Q.Atmospheric correction of remote sensing imagery based on the surface spectrum′s vector space［J］.Science China Earth Science，2012，55（1）：1－8.

［69］ CHEN D，ZHANG L Q，ZHANG M.A mathematical morphologybased multi－level filter for Generating DTMs［J］.Science China Information Sciences.2012.1－14（doi：10.1007／s11432－012－4707－3）.

［70］ XIE J H，ZHANG L Q，LI J，et al.Automatic simplification and visualization of 3Durban building models［J］.International Journal of Applied Earth Observation and Geoinformation，2012，14（1）：222－231.

［71］ YANG Y Z，WU L X，GUO J T，et al.Reasearch on Distributed Hilbert R－Tree Spatial Index Based on BIRCH Clustering［C］.The 20th International Conference on Geoinformatics，2012.

［72］ ZHANG Z.Automated plotting technology research for the point symbols in the multi－core environment［C］.The 20th International Conference on Geoinformatics，2012.

［73］ ZHONG Y Q，HAN J Z，ZHANG T Y，et al.Towards parallel spatial query processing for big spatial data［A］.Proceedings of the 26th IEEE International Parallel ＆Distributed Processing Symposium［C］.2012.

［74］ PAN X，ZHANG S Q.Parallelized remote sensing classifier based on rough set theory algorithm［C］.The 20th International Conference on Geoinformatics，2012.

［75］ YAN Z Y，SONG Q F.An implementation of parallel Floyd－Warshall algorithm based on hybrid MPI and OpenMP［C］.The 2nd International Conference on Electronics，Communications and Control（ICECC 2012），2012.

［76］ ZHAN L J，QIN C Z.A graph－theory－based method for parallelizing the multiple－flow－direction algorithm on CUDA compatible graphics processing units［C］.2011 1st IEEE International Conference on Spatial Data Mining and Geographical Knowledge Services，in Conjunction with 8th Beijing International Workshop on Geographical Information Science，2011.

［77］江锦成，郭甲腾，吴立新，等.三维地学实体多粒度栅格剖分与布尔运算的并行算法［J］.科技导报，2011，29（35）：18－23.

［78］朱效民，赵红超，方金云，等.鲁棒高效的矢量地图叠加分析算法［J］.遥感学报，2012，16（3）：448－465.

［79］王阳，李连发.空间贝叶斯分类器并行化［J］.地理与地理信息科学，2013，29（4）：47－51.

［80］马益杭，占利军，谢传节，等.连通域标记算法的并行化研究［J］.地理与地理信息科学，2013，29（4）：67－71.

［81］王维一，裴韬，秦承志.栅格地理数据模糊C均值聚类算法的并行化研究［J］.地理与地理信息科学，2013，29（4）：77－80.

［82］潘欣，杨典华，张树清，等.面向超大型栅格数据的并行快速傅里叶变换算法［J］.地理与地理信息科学，2013，29（4）：52－55.

［83］张树清，张策，杨典华，等.简单要素模型下的多边形对象叠加并行运算策略研究［J］.地理与地理信息科学，2013，29（4）：43－46.

［84］薄海光，吴立新，余接情，等.基于GPU加速的SDOG并行可视化实验［J］.地理与地理信息科学，2013，29（4）：72－76.

［85］杨宜舟，吴立新，郭甲腾，等.一种实现拓扑关系高效并行计算的矢量数据划分方法［J］.地理与地理信息科学，2013，29（4）：25－29.

［86］江锦成，吴立新，孙文彬，等.点集V图－K阶邻近并行搜索算法设计与实验［J］.地理与地理信息科学，2013，29（4）：30－34.

［87］闫志远，孙文彬，周长江，等.基于并行分散搜索的p－中心定位算法［J］.地理与地理信息科学，2013，29（4）：39－42.

［88］孙文彬，谭正龙，王江，等.最短路径算法的并行化策略分析［J］.地理与地理信息科学，2013，29（4）：17－20.