Spatial strategies for parallel spatial modelling

Abstract

Abstract. To achieve high levels of performance in parallel geoprocessing, the underlying spatial structure and relations of spatial models must be accounted for and exploited during decomposition into parallel processes. Spatial models are classified from two perspectives, the domain of modelling and the scope of operations, and a framework of strategies is developed to guide the decomposition of models with different characteristics into parallel processes. Two models are decomposed using these strategies: hill-shading on digital elevation models and the construction of Delaunay Triangulations. Performance statistics are presented for implementations of these algorithms on a MIMD computer.     

Parallel optimal choropleth map classification in PySAL

In this article, we report on our experiences with refactoring a spatial analysis library to support parallelization. Python Spatial Analysis Library (PySAL) is a library of spatial analytical functions written in the open-source language, Python. As part of a larger scale effort toward developing cyberinfrastructure of GIScience, we examine the particular case of choropleth map classification through alternative parallel implementations of the Fisher-Jenks optimal classification method using a multi-core, single desktop environment. The implementations rely on three different parallel Python libraries, PyOpenCL, Parallel Python, (PP) and Multiprocessing. Our results point to the dominance of the CPU-based Parallel Python and Multiprocessing implementations over the Graphical Processing Unit (GPU)-based PyOpenCL approach.     

GIS中的模糊形态运算

空间数据的不确定性是当前GIS领域的研究难点之一。为了描述空间数据的模糊性,把模糊集理论引入GIS,以加强GIS对模糊现象建模的能力,因而产生了模糊数据。但现有GIS缺乏对模糊数据分析和处理的能力。该文把模糊集理论引入数学形态学,提出能处理模糊数据的模糊形态运算,并给出模糊形态运算的隶属函数,使传统的数学形态学能够处理模糊数据且容易在计算机上实现。     

Strategies for real-time spatial analysis using massively parallel SIMD computers: an application to urban traffic flow analysis

Abstract

The current research focuses upon the development of a methodology for undertaking real-time spatial analysis in a supercomputing environment, specifically using massively parallel SIMD computers. Several approaches that can be used to explore the parallelization characteristics of spatial problems are introduced. Within the focus of a methodology directed toward spatial data parallelism, strategies based on both location-based data decomposition and object-based data decomposition are proposed and a programming logic for spatial operations at local, neighborhood and global levels is also recommended. An empirical study of real-time traffic flow analysis shows the utility of the suggested approach for a complex, spatial analysis situation. The empirical example demonstrates that the proposed methodology, especially when combined with appropriate programming strategies, is preferable in situations where critical, real-time, spatial analysis computations are required. The implementation of this example in a parallel environment also points out some interesting theoretical questions with respect to the theoretical basis underlying the analysis of large networks.     

A parallel method to accelerate spatial operations involving polygon intersections

Polygon intersection is an important spatial data-handling process, on which many spatial operations are based. However, this process is computationally intensive because it involves the detection and calculation of polygon intersections. We addressed this computation issue based on two perspectives. First, we improved a method called boundary algebra filling to efficiently rasterize the input polygons. Polygon intersections were subsequently detected in the cells of the raster. Owing to the use of a raster data structure, this method offers advantages of reduced task dependence and improved performance. Based on this method, we developed parallel strategies for different procedures in terms of workload decomposition and task scheduling. Thus, the workload across different parallel processes can be balanced. The results suggest that our method can effectively accelerate the process of polygon intersection. When addressing datasets with 1,409,020 groups of overlapping polygons, our method could reduce the total execution time from 987.82 to 53.66 s, thereby obtaining an optimal speedup ratio of 18.41 while consistently balancing the workloads. We also tested the effect of task scheduling on the parallel efficiency, showing that reducing the total runtime is effective, especially for a lower number of processes. Finally, the good scalability of the method is demonstrated.     

A machine learning approach for predicting computational intensity and domain decomposition in parallel geoprocessing

ABSTRACT

High performance computing is required for fast geoprocessing of geospatial big data. Using spatial domains to represent computational intensity (CIT) and domain decomposition for parallelism are prominent strategies when designing parallel geoprocessing applications. Traditional domain decomposition is limited in evaluating the computational intensity, which often results in load imbalance and poor parallel performance. From the data science perspective, machine learning from Artificial Intelligence (AI) shows promise for better CIT evaluation. This paper proposes a machine learning approach for predicting computational intensity, followed by an optimized domain decomposition, which divides the spatial domain into balanced subdivisions based on the predicted CIT to achieve better parallel performance. The approach provides a reference framework on how various machine learning methods including feature selection and model training can be used in predicting computational intensity and optimizing parallel geoprocessing against different cases. Some comparative experiments between the approach and traditional methods were performed using the two cases, DEM generation from point clouds and spatial intersection on vector data. The results not only demonstrate the advantage of the approach, but also provide hints on how traditional GIS computation can be improved by the AI machine learning.     

Fundamental operations in computer-assisted map analysis

Abstract

Geographical information systems (GIS) provide capabilities for the mapping, management and analysis of cartographic information. Unlike most other disciplines, GIS technology was born from specialized applications. A comprehensive theory relating the various techniques used in these applications is only now emerging. By organizing the set of analytic methods into a mathematical structure, a generalized framework for cartographic modelling is developed. Within this framework, users logically order primitive operators on map variables in a manner analogous to traditional algebra and statistics. This paper describes the fundamental classes of operations used in computer-assisted map analysis. Several of the procedures are demonstrated using a fourth-generation computer language for personal computers.     

Massively parallel spatial point pattern analysis: Ripley’s K function accelerated using graphics processing units

This study presents a massively parallel spatial computing approach that uses general-purpose graphics processing units (GPUs) to accelerate Ripley’s K function for univariate spatial point pattern analysis. Ripley’s K function is a representative spatial point pattern analysis approach that allows for quantitatively evaluating the spatial dispersion characteristics of point patterns. However, considerable computation is often required when analyzing large spatial data using Ripley’s K function. In this study, we developed a massively parallel approach of Ripley’s K function for accelerating spatial point pattern analysis. GPUs serve as a massively parallel platform that is built on many-core architecture for speeding up Ripley’s K function. Variable-grained domain decomposition and thread-level synchronization based on shared memory are parallel strategies designed to exploit concurrency in the spatial algorithm of Ripley’s K function for efficient parallelization. Experimental results demonstrate that substantial acceleration is obtained for Ripley’s K function parallelized within GPU environments.     

Cartographic Visualization: An Assessment and Epistemological Review*

This article examines the concept of cartographic visualization. The value of cartographic visualization as an essential component in the study of geographic phenomena is discussed. Ontological and epistemological perspectives are addressed, with examinations of positivist, realist, postmodern, feminist, and anarchist approaches to visualization. Critiques of cartographic visualization from social theorists and quantitative positivists are presented. The author asserts that cartographic visualization is not restricted to any one particular epistemological framework but may combine methods of knowledge production. For comprehensive analysis of spatial data, cartographic visualization must be included along with other qualitative and quantitative analysis.     

Methods for visualizing the explosive remnants of war

This study aimed to answer the question how cartography can help decision makers visualize the problem of contamination by explosive remnants of war (ERW). We thus explored a set of six cartographic visualization methods and systematically evaluated their usefulness with respect to four categories of stakeholders in the humanitarian demining process (i.e., database administrators, operations officers, directors of national mine action authorities, and donors) at four geographical scales, ranging from municipal to global. The main application of our work is for stakeholders involved in humanitarian demining. We provide them with a comprehensive framework for visualizing ERW hazards at the geographical scale at which they have to make decisions, as well as customized cartographic visualization tools and recommendations to help them make informed decisions. For example, we provide potential donors with a method for obtaining a global overview of ERW contamination while remaining aware of regional variation and hot spots. We also enhance cartographic visualization capabilities using traditional kernel density estimation by customizing key parameters. Specifically, we propose a method for adjusting kernel bandwidth for datasets with highly heterogeneous spatial distributions and a method for generating kernel surfaces from polygon data that consists of infilling the polygons with points before using them as inputs in the kernel density estimation.     

A general-purpose parallel raster processing programming library test application using a geographic cellular automata model

A general-purpose parallel raster processing programming library (pRPL) was developed and applied to speed up a commonly used cellular automaton model with known tractability limitations. The library is suitable for use by geographic information scientists with basic programming skills, but who lack knowledge and experience of parallel computing and programming. pRPL is a general-purpose programming library that provides generic support for raster processing, including local-scope, neighborhood-scope, regional-scope, and global-scope algorithms as long as they are parallelizable. The library also supports multilayer algorithms. Besides the standard data domain decomposition methods, pRPL provides a spatially adaptive quad-tree-based decomposition to produce more evenly distributed workloads among processors. Data parallelism and task parallelism are supported, with both static and dynamic load-balancing. By grouping processors, pRPL also supports data–task hybrid parallelism, i.e., data parallelism within a processor group and task parallelism among processor groups. pSLEUTH, a parallel version of a well-known cellular automata model for simulating urban land-use change (SLEUTH), was developed to demonstrate full utilization of the advanced features of pRPL. Experiments with real-world data sets were conducted and the performance of pSLEUTH measured. We conclude not only that pRPL greatly reduces the development complexity of implementing a parallel raster-processing algorithm, it also greatly reduces the computing time of computationally intensive raster-processing algorithms, as demonstrated with pSLEUTH.     

A formal framework for the representation of stack-based terrains

This paper presents a formal framework for the representation of three-dimensional geospatial data and the definition of common geographic information system (GIS) spatial operations. We use the compact stack-based representation of terrains (SBRT) in order to model geological volumetric data, both at the surface and subsurface levels, thus preventing the large storage requirements of regular voxel models. The main contribution of this paper is fitting the SBRT into the geo-atom theory in a seamless way, providing it with a sound formal geographic foundation. In addition we have defined a set of common spatial operations on this representation using the tools provided by map algebra. More complex geoprocessing operations or geophysical simulations using the SBRT as representation can be implemented as a composition of these fundamental operations. Finally a data model and an implementation extending the coverage concept provided by the Geography Markup Language standard are suggested. Geoscientists and GIS professionals can take advantage of this model to exchange and reuse geoinformation within a well-specified framework.     

Coordinating hazardous waste management activities using geographical information systems

Abstract

This paper describes a framework for the role of geographical information systems (GIS) in the monitoring and management of hazardous waste sites. Compilation of required information, incorporation of existing strategies for waste monitoring, analysis of these data in a GIS environment and the integration of computerized models for transport processes are discussed. Examples for the analysis of spatial data using techniques of cartographic overlay and the implementation of geo-statistical methods on monitoring data are provided from work in progress by the authors. These examples are set in the context of developing a fully integrated monitoring and management system utilizing GIS technology.     

Supercapitalism: The Transformation of Business,Democracy, and Everyday Life

While linguistic diversity is an integral component of cultural landscapes, the spatial depiction of languages fails to represent all community members. Language is difficult to map and established guidelines are lacking. The perception of power conveyed is arguably the most meaningful design issue in language mapping, as most language maps inaccurately show one language per place. This research examines the cartographic visualization of linguistic diversity, contributing to our understanding of the perception of power through cartographic decisions, with the application of a linguistic diversity index. The resulting maps serve as new figures for linguistic diversity lessons in educational contexts.     

A Review of: “Applications of Spatial Data Structures: Computer Graphics,Image Processing,and GIS”. By H. SAMET. (Addison-Wesley Publishing Company,Inc, 1989.) [Pp. xv + 507; figures,tables, appendix,references, name and credit index,subject index.] Price US $49.95. ISBN 020150300 X (hardback).

The introduction of automated generalisation procedures in map production systems requires that generalisation systems are capable of processing large amounts of map data in acceptable time and that cartographic quality is similar to traditional map products. With respect to these requirements, we examine two complementary approaches that should improve generalisation systems currently in use by national topographic mapping agencies. Our focus is particularly on self‐evaluating systems, taking as an example those systems that build on the multi‐agent paradigm. The first approach aims to improve the cartographic quality by utilising cartographic expert knowledge relating to spatial context. More specifically, we introduce expert rules for the selection of generalisation operations based on a classification of buildings into five urban structure types, including inner city, urban, suburban, rural, and industrial and commercial areas. The second approach aims to utilise machine learning techniques to extract heuristics that allow us to reduce the search space and hence the time in which a good cartographical solution is reached. Both approaches are tested individually and in combination for the generalisation of buildings from map scale 1:5000 to the target map scale of 1:25 000. Our experiments show improvements in terms of efficiency and effectiveness. We provide evidence that both approaches complement each other and that a combination of expert and machine learnt rules give better results than the individual approaches. Both approaches are sufficiently general to be applicable to other forms of self‐evaluating, constraint‐based systems than multi‐agent systems, and to other feature classes than buildings. Problems have been identified resulting from difficulties to formalise cartographic quality by means of constraints for the control of the generalisation process.     

GIS空间动态模型组件的设计与实现

组件重用技术为GIS与空间模型的集成提供了新的解决方案。该文设计的空间动态模型的GIS组件 -Dy namicGC ,它在传统GIS数据模型的基础上 ,增加了表达空间动态系统的过程和关系 (流 )的数据模型和对象接口 ,为GIS环境下创建复杂动态过程模型提供了新的工具和解决方案。该组件基于微软组件对象模型 (COM/DCOM)实现 ,充分考虑了互操作性、模型建模语言以及模型系统的可获取性需求 ,由一系列支持动态数据计算的OLE自动化对象集组成 ,可支持VB、Dephi、VisualC 等通用开发环境 ,也支持VBA、VBSCRIPT、JAVASCRIPT等脚本语言环境。使用VBA创建了经典的“生命游戏”的元胞自动机模型的实现 ,作为该组件创建动态过程模型的应用实例。     

Road network simplification with knowledge-based spatial analysis

A typical requirement in digital society is the rapid distribution and effective application of digital products. Geographical data bases are far more complex than other ones in that both attribute and spatial data have to be stored and handled under the same framework. On the other hand, the number of end users of digital cartographic data is explosively increasing, ranging from professional map makers to vehicle drivers and individual tourists. Thus arises a question: how can a data supplier give the “best” service to each user? In nature it involves such difficult problems as cartographic generalization and map simplification. In this paper, the author argues that the visual knowledge or perception experience can be effectively exploited and used to guide the process of data simplification. We have developed a prototype system with a subset of the vector road database covering Munich city.

     

A new approach to pre-stack seismic processing

Pre-stack processing of seismic reflection data is significantly simplified if the data organization is the same as that in which the data were acquired in the field; that is, in time slices through common-source gathers. For an impulsive source, the entire processing stream reduces to two elements: velocity analysis and reverse-time pre-stack migration. Many of the steps that are applied as independent operations in standard processing (including demultiplexing, sorting into common-midpoint gathers, elevation corrections, near-surface velocity static corrections, first break muting, ground roll removal, and both normal and dip move-out corrections) either are eliminated, or are applied implicitly during migration. This approach is ideally suited to parallel processing, and can be implemented in machines with small processor memories.     

分布式水文模型的并行计算研究进展

大流域、高分辨率、多过程耦合的分布式水文模拟计算量巨大,传统串行计算技术不能满足其对计算能力的需求,因此需要借助于并行计算的支持。本文首先从空间、时间和子过程三个角度对分布式水文模型的可并行性进行了分析,指出空间分解的方式是分布式水文模型并行计算的首选方式,并从空间分解的角度对水文子过程计算方法和分布式水文模型进行了分类。然后对分布式水文模型的并行计算研究现状进行了总结。其中,在空间分解方式的并行计算方面,现有研究大多以子流域作为并行计算的基本调度单元;在时间角度的并行计算方面,有学者对时空域双重离散的并行计算方法进行了初步研究。最后,从并行算法设计、流域系统综合模拟的并行计算框架和支持并行计算的高性能数据读写方法3个方面讨论了当前存在的关键问题和未来的发展方向。     

地图可视化研究

建立在计算机技术基础上的地图可视化是现代地图学的核心内容之一。文章从分析地图可视化的含义出发,提出了地图可视化研究的一个基本框架,同时简要分析了地图可视化的特点。认为地图可视化的主要研究领域有:可视化变量研究、可视化分类研究、时空数据结构研究、视觉感受与视觉效果研究、虚拟现实研究、空间认知与信息传输研究等 6个方面。最后,就北京地区地形三维可视化实践作了简单介绍。