A parallel computing approach to viewshed analysis of large terrain data using graphics processing units

Viewshed analysis, often supported by geographic information system, is widely used in many application domains. However, as terrain data continue to become increasingly large and available at high resolutions, data-intensive viewshed analysis poses significant computational challenges. General-purpose computation on graphics processing units (GPUs) provides a promising means to address such challenges. This article describes a parallel computing approach to data-intensive viewshed analysis of large terrain data using GPUs. Our approach exploits the high-bandwidth memory of GPUs and the parallelism of massive spatial data to enable memory-intensive and computation-intensive tasks while central processing units are used to achieve efficient input/output (I/O) management. Furthermore, a two-level spatial domain decomposition strategy has been developed to mitigate a performance bottleneck caused by data transfer in the memory hierarchy of GPU-based architecture. Computational experiments were designed to evaluate computational performance of the approach. The experiments demonstrate significant performance improvement over a well-known sequential computing method, and an enhanced ability of analyzing sizable datasets that the sequential computing method cannot handle.     

A data model for moving regions of fixed shape in databases

Moving object databases are designed to store and process spatial and temporal object data. An especially useful moving object type is a moving region, which consists of one or more moving polygons suitable for modeling the spread of forest fires, the movement of clouds, spread of diseases and many other real-world phenomena. Previous implementations usually allow a changing shape of the region during the movement; however, the necessary restrictions on this model result in an inaccurate interpolation of rotating objects. In this paper, we present an alternative approach for moving and rotating regions of fixed shape, called Fixed Moving Regions, which provide a significantly better model for a wide range of applications like modeling the movement of oil tankers, icebergs and other rigid structures. Furthermore, we describe and implement several useful operations on this new object type to enable a database system to solve many real-world problems, as for example collision tests, projections and intersections, much more accurate than with other models. Based on this research, we also implemented a library for easy integration into moving objects database systems, as for example the DBMS Secondo (1) (2) developed at the FernUniversität in Hagen.     

Parallelization of a regionalization heuristic in distributed computing platforms – a case study of parallel-p-compact-regions problem

In this paper, we report efforts to develop a parallel implementation of the p-compact regionalization problem suitable for multi-core desktop and high-performance computing environments. Regionalization for data aggregation is a key component of many spatial analytical workflows that are known to be NP-Hard. We utilize a low communication cost parallel implementation technique that provides a benchmark for more complex implementations of this algorithm. Both the initialization phase, utilizing a Memory-based Randomized Greedy and Edge Reassignment (MERGE) algorithm, and the local search phase, utilizing Simulated Annealing, are distributed over available compute cores. Our results suggest that the proposed parallelization strategy is capable of solving the compactness-driven regionalization problem both efficiently and effectively. We expect this work to advance CyberGIS research by extending its application areas into the regionalization world and to make a contribution to the spatial analysis community by proposing this parallelization strategy to solve large regionalization problems efficiently.     

Visual analytics of delays and interaction in movement data

The analysis of interaction between movement trajectories is of interest for various domains when movement of multiple objects is concerned. Interaction often includes a delayed response, making it difficult to detect interaction with current methods that compare movement at specific time intervals. We propose analyses and visualizations, on a local and global scale, of delayed movement responses, where an action is followed by a reaction over time, on trajectories recorded simultaneously. We developed a novel approach to compute the global delay in subquadratic time using a fast Fourier transform (FFT). Central to our local analysis of delays is the computation of a matching between the trajectories in a so-called delay space. It encodes the similarities between all pairs of points of the trajectories. In the visualization, the edges of the matching are bundled into patches, such that shape and color of a patch help to encode changes in an interaction pattern. To evaluate our approach experimentally, we have implemented it as a prototype visual analytics tool and have applied the tool on three bidimensional data sets. For this we used various measures to compute the delay space, including the directional distance, a new similarity measure, which captures more complex interactions by combining directional and spatial characteristics. We compare matchings of various methods computing similarity between trajectories. We also compare various procedures to compute the matching in the delay space, specifically the Fréchet distance, dynamic time warping (DTW), and edit distance (ED). Finally, we demonstrate how to validate the consistency of pairwise matchings by computing matchings between more than two trajectories.     

Using a Computational Grid for Geographic Information Analysis: A Reconnaissance

High performance computing has undergone a radical transformation during the past decade. Though monolithic supercomputers continue to be built with significantly increased computing power, geographically distributed computing resources are now routinely linked using high‐speed networks to address a broad range of computationally complex problems. These confederated resources are referred to collectively as a computational Grid. Many geographical problems exhibit characteristics that make them candidates for this new model of computing. As an illustration, we describe a spatial statistics problem and demonstrate how it can be addressed using Grid computing strategies. A key element of this application is the development of middleware that handles domain decomposition and coordinates computational functions. We also discuss the development of Grid portals that are designed to help researchers and decision makers access and use geographic information analysis tools.     

Spatial optimization for regionalization problems with spatial interaction: a heuristic approach

Spatial optimization techniques are commonly used for regionalization problems, often represented as p-regions problems. Although various spatial optimization approaches have been proposed for finding exact solutions to p-regions problems, these approaches are not practical when applied to large-size problems. Alternatively, various heuristics provide effective ways to find near-optimal solutions for p-regions problem. However, most heuristic approaches are specifically designed for particular geographic settings. This paper proposes a new heuristic approach named Automated Zoning Procedure-Center Interchange (AZP-CI) to solve the p-functional regions problem (PFRP), which constructs regions by combining small areas that share common characteristics with predefined functional centers and have tight connections among themselves through spatial interaction. The AZP-CI consists of two subprocesses. First, the dissolving/splitting process enhances diversification and thereby produces an extensive exploration of the solution space. Second, the standard AZP locally improves the objective value. The AZP-CI was tested using randomly simulated datasets and two empirical datasets with different sizes. These evaluations indicate that AZP-CI outperforms two established heuristic algorithms: the AZP and simulated annealing, in terms of both solution quality and consistency of producing reliable solutions regardless of initial conditions. It is also noted that AZP-CI, as a general heuristic method, can be easily extended to other regionalization problems. Furthermore, the AZP-CI could be a more scalable algorithm to solve computational intensive spatial optimization problems when it is combined with cyberinfrastructure.     

Predicting the visualization intensity for interactive spatio-temporal visual analytics: a data-driven view-dependent approach

The continually increasing size of geospatial data sets poses a computational challenge when conducting interactive visual analytics using conventional desktop-based visualization tools. In recent decades, improvements in parallel visualization using state-of-the-art computing techniques have significantly enhanced our capacity to analyse massive geospatial data sets. However, only a few strategies have been developed to maximize the utilization of parallel computing resources to support interactive visualization. In particular, an efficient visualization intensity prediction component is lacking from most existing parallel visualization frameworks. In this study, we propose a data-driven view-dependent visualization intensity prediction method, which can dynamically predict the visualization intensity based on the distribution patterns of spatio-temporal data. The predicted results are used to schedule the allocation of visualization tasks. We integrated this strategy with a parallel visualization system deployed in a compute unified device architecture (CUDA)-enabled graphical processing units (GPUs) cloud. To evaluate the flexibility of this strategy, we performed experiments using dust storm data sets produced from a regional climate model. The results of the experiments showed that the proposed method yields stable and accurate prediction results with acceptable computational overheads under different types of interactive visualization operations. The results also showed that our strategy improves the overall visualization efficiency by incorporating intensity-based scheduling.     

分布式水文模型软件系统研究综述

分布式水文模型软件系统作为分布式水文模型的技术外壳,是模型应用的重要技术保障。当前分布式水文模型应用呈现出多过程综合模拟、用户群范围广和计算量大的特点,对分布式水文模型软件系统的灵活性、易用性和高效性提出了更高的要求。本文首先分析了分布式水文模型应用的主要流程,之后从应用视角对现有分布式水文模型软件系统的特点进行了归纳,主要结论为:①软件系统按照模型结构灵活性的高低分为以下3种类型:不支持子过程选择和算法设置,不支持子过程选择、但支持算法设置,同时支持子过程选择和算法设置;②根据用户操作数据预处理软件方式的不同,参数提取方式分为菜单/命令行式和向导式;③按照模型的程序实现方法分为串行和并行方式,按照模型运行环境分为本地和网络模式。现有软件系统在灵活性、易用性和高效性方面存在如下问题:一是尚未解决模型结构灵活性和对用户知识依赖性之间的矛盾;二是现有菜单/命令行式和向导式的参数提取方式步骤繁琐,难以实现参数的自动提取;三是模型大多为串行方式和本地模式,容易遇到计算瓶颈问题。最后从模块化、智能化、网络化及移动化、并行化和虚拟仿真等方面探讨了分布式水文模型软件系统的发展趋势和研究方向。     

An algorithm for on-the-fly K shortest paths finding in multi-storey buildings using a hierarchical topology model

This article presents an approach to computing K shortest paths in large buildings with complex horizontal and vertical connectivity. The building topology is obtained from Building Information Model (BIM) and implemented using directed multigraphs. Hierarchical design allows the calculation of feasible paths without the need to load into memory the topology of the entire building. It is possible to expand the graph with new connectivity on-the-fly. The paths calculated may be composed of traversable building components that are located inside the buildings or those that are both inside and outside buildings. The performance (computational time and heap size used) is optimized by using the appropriate collections (maps, lists and sets). The proposed algorithm is evaluated in several use-case scenarios – complete graphs and real building environments. In all test scenarios, the proposed path finding algorithm is faster and uses less memory when compared to the fast version of the Yen’s KSP algorithm. The proposed approach can be successfully used as a first level of coarse-to-fine path finding algorithms.     

A spatially adaptive decomposition approach for parallel vector data visualization of polylines and polygons

With the wide adoption of big spatial data and the emergence of CyberGIS, the nontrivial computational intensity introduced by massive amount of data poses great challenges to the performance of vector map visualization. The parallel computing technologies provide promising solutions to such problems. Evenly decomposing the visualization task into multiple subtasks is one of the key issues in parallel visualization of vector data. This study focuses on the decomposition of polyline and polygon data for parallel visualization. Two key factors impacting the computational intensity were identified: the number of features and the number of vertices of each feature. The computational intensity transform functions (CITFs) were constructed based on the linear relationships between the factors and the computing time. The computational intensity grid (CIG) can then be constructed using the CITFs to represent the spatial distribution of computational intensity. A noninterlaced continuous space-filling curve is used to group the lattices of CIG into multiple sub-domains such that each sub-domain entails the same amount of computational intensity as others. The experiments demonstrated that the approach proposed in this paper was able to effectively estimate and spatially represent the computational intensity of visualizing polylines and polygons. Compared with the regular domain decomposition methods, the new approach generated much more balanced decomposition of computational intensity for parallel visualization and achieved near-linear speedups, especially when the data is greatly heterogeneously distributed in space.     

Using adaptively coupled models and high-performance computing for enabling the computability of dust storm forecasting

Forecasting dust storms for large geographical areas with high resolution poses great challenges for scientific and computational research. Limitations of computing power and the scalability of parallel systems preclude an immediate solution to such challenges. This article reports our research on using adaptively coupled models to resolve the computational challenges and enable the computability of dust storm forecasting by dividing the large geographical domain into multiple subdomains based on spatiotemporal distributions of the dust storm. A dust storm model (Eta-8bin) performs a quick forecasting with low resolution (22 km) to identify potential hotspots with high dust concentration. A finer model, non-hydrostatic mesoscale model (NMM-dust) performs high-resolution (3 km) forecasting over the much smaller hotspots in parallel to reduce computational requirements and computing time. We also adopted spatiotemporal principles among computing resources and subdomains to optimize parallel systems and improve the performance of high-resolution NMM-dust model. This research enabled the computability of high-resolution, large-area dust storm forecasting using the adaptively coupled execution of the two models Eta-8bin and NMM-dust.     

景观生态区划的理论研究

景观生态系统由多个层次水平的等级体系所组成, 在不同的时间和空间尺度中, 其结构与 功能具有不同的相互依存关系, 区划的概念有助于整合景观的等级性并厘清复杂性。本研究在景 观生态学格局、过程、功能研究的基础上, 结合综合自然地理区划、生态区划、生态经济区划、农业 区划等相关研究的成果,探讨了景观生态区划应依循的原则、内容及区划等级系统, 指出景观生 态区划不仅强调景观水平方向上的空间异质性, 还必须综合景观单元的过程关联和功能统一性。 同时以生态系统完整性原则为核心制定了开展景观生态区划需遵循的等级性、多尺度性、发生一 致性、格局与功能依存性、功能协调性以及界线完整性等原则。在其指导下, 重点讨论了景观生态 区划过程中涉及的方法论构建、景观生态分析与评价、景观生态区划体系构建等研究内容。最后, 通过比较了景观生态区划与自然区划、生态区划以及经济区划之间的异同,提出了不同尺度下景 观生态区划理论的应用方向。     

Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees

Regionalization is a classification procedure applied to spatial objects with an areal representation, which groups them into homogeneous contiguous regions. This paper presents an efficient method for regionalization. The first step creates a connectivity graph that captures the neighbourhood relationship between the spatial objects. The cost of each edge in the graph is inversely proportional to the similarity between the regions it joins. We summarize the neighbourhood structure by a minimum spanning tree (MST), which is a connected tree with no circuits. We partition the MST by successive removal of edges that link dissimilar regions. The result is the division of the spatial objects into connected regions that have maximum internal homogeneity. Since the MST partitioning problem is NP‐hard, we propose a heuristic to speed up the tree partitioning significantly. Our results show that our proposed method combines performance and quality, and it is a good alternative to other regionalization methods found in the literature.     

A high-performance cellular automata model for urban simulation based on vectorization and parallel computing technology

Cellular automata (CA) models can simulate complex urban systems through simple rules and have become important tools for studying the spatio-temporal evolution of urban land use. However, the multiple and large-volume data layers, massive geospatial processing and complicated algorithms for automatic calibration in the urban CA models require a high level of computational capability. Unfortunately, the limited performance of sequential computation on a single computing unit (i.e. a central processing unit (CPU) or a graphics processing unit (GPU)) and the high cost of parallel design and programming make it difficult to establish a high-performance urban CA model. As a result of its powerful computational ability and scalability, the vectorization paradigm is becoming increasingly important and has received wide attention with regard to this kind of computational problem. This paper presents a high-performance CA model using vectorization and parallel computing technology for the computation-intensive and data-intensive geospatial processing in urban simulation. To transfer the original algorithm to a vectorized algorithm, we define the neighborhood set of the cell space and improve the operation paradigm of neighborhood computation, transition probability calculation, and cell state transition. The experiments undertaken in this study demonstrate that the vectorized algorithm can greatly reduce the computation time, especially in the environment of a vector programming language, and it is possible to parallelize the algorithm as the data volume increases. The execution time for the simulation of 5-m resolution and 3 × 3 neighborhood decreased from 38,220.43 s to 803.36 s with the vectorized algorithm and was further shortened to 476.54 s by dividing the domain into four computing units. The experiments also indicated that the computational efficiency of the vectorized algorithm is closely related to the neighborhood size and configuration, as well as the shape of the research domain. We can conclude that the combination of vectorization and parallel computing technology can provide scalable solutions to significantly improve the applicability of urban CA.     

对全球变化背景下构建生态地理区域系统的若干认识

研究复杂的人地系统,研究区域的可持续发展需要有一个比较适当的区域划分。全球变化问题研究的水平也取决于对地域差异认识的深度。因此,建立中国生态地理区域系统,探讨其在全球变化中的应用,可为区域发展与陆地生态系统关系的研究提供科学的区域框架。本文从理论基础、必要性、目的、意义、界线、指标和方法论等方面探讨了有关生态地理区划的若干问题。     

A GPU-accelerated adaptive kernel density estimation approach for efficient point pattern analysis on spatial big data

Kernel density estimation (KDE) is a classic approach for spatial point pattern analysis. In many applications, KDE with spatially adaptive bandwidths (adaptive KDE) is preferred over KDE with an invariant bandwidth (fixed KDE). However, bandwidths determination for adaptive KDE is extremely computationally intensive, particularly for point pattern analysis tasks of large problem sizes. This computational challenge impedes the application of adaptive KDE to analyze large point data sets, which are common in this big data era. This article presents a graphics processing units (GPUs)-accelerated adaptive KDE algorithm for efficient spatial point pattern analysis on spatial big data. First, optimizations were designed to reduce the algorithmic complexity of the bandwidth determination algorithm for adaptive KDE. The massively parallel computing resources on GPU were then exploited to further speed up the optimized algorithm. Experimental results demonstrated that the proposed optimizations effectively improved the performance by a factor of tens. Compared to the sequential algorithm and an Open Multiprocessing (OpenMP)-based algorithm leveraging multiple central processing unit cores for adaptive KDE, the GPU-enabled algorithm accelerated point pattern analysis tasks by a factor of hundreds and tens, respectively. Additionally, the GPU-accelerated adaptive KDE algorithm scales reasonably well while increasing the size of data sets. Given the significant acceleration brought by the GPU-enabled adaptive KDE algorithm, point pattern analysis with the adaptive KDE approach on large point data sets can be performed efficiently. Point pattern analysis on spatial big data, computationally prohibitive with the sequential algorithm, can be conducted routinely with the GPU-accelerated algorithm. The GPU-accelerated adaptive KDE approach contributes to the geospatial computational toolbox that facilitates geographic knowledge discovery from spatial big data.     

Computational improvements to multi-scale geographically weighted regression

ABSTRACT

Geographically Weighted Regression (GWR) has been broadly used in various fields to model spatially non-stationary relationships. Multi-scale Geographically Weighted Regression (MGWR) is a recent advancement to the classic GWR model. MGWR is superior in capturing multi-scale processes over the traditional single-scale GWR model by using different bandwidths for each covariate. However, the multiscale property of MGWR brings additional computation costs. The calibration process of MGWR involves iterative back-fitting under the additive model (AM) framework. Currently, MGWR can only be applied on small datasets within a tolerable time and is prohibitively time-consuming to run with moderately large datasets (greater than 5,000 observations). In this paper, we propose a parallel implementation that has crucial computational improvements to the MGWR calibration. This improved computational method reduces both memory footprint and runtime to allow MGWR modelling to be applied to moderate-to-large datasets (up to 100,000 observations). These improvements are integrated into the mgwr python package and the MGWR 2.0 software, both of which are freely available to download.     

Calibration of Genetic Algorithm Parameters for Mining-Related Optimization Problems

Genetic algorithms (GA) are widely used to solve engineering optimization problems. The quality and performance of the solution generated strongly depend on the selection of the GA parameter values (crossover and mutation rates and population size). We propose an approach based on full factorial and response surface methodology experimental designs to calibrate GA parameters such that the objective function is maximized/minimized and the relative importance of the parameters is quantified. The approach was tested by applying it to stope optimization of underground mines, where profit can vary ±?7% based solely on GA parameters. Results showed that: (1) a larger population size did not always increase solution time; (2) solution time was positively related to crossover and mutation rates; and (3) simultaneous analysis of solution time and profit illustrated the trade-off between acceptable computing time and profit desirability through GA parameter selection. This approach can be used to calibrate parameters of other metaheuristics.

     

Hyperparameter optimization of neural network-driven spatial models accelerated using cyber-enabled high-performance computing

Artificial neural networks (ANNs) have been extensively used for the spatially explicit modeling of complex geographic phenomena. However, because of the complexity of the computational process, there has been an inadequate investigation on the parameter configuration of neural networks. Most studies in the literature from GIScience rely on a trial-and-error approach to select the parameter setting for ANN-driven spatial models. Hyperparameter optimization provides support for selecting the optimal architectures of ANNs. Thus, in this study, we develop an automated hyperparameter selection approach to identify optimal neural networks for spatial modeling. Further, the use of hyperparameter optimization is challenging because hyperparameter space is often large and the associated computational demand is heavy. Therefore, we utilize high-performance computing to accelerate the model selection process. Furthermore, we involve spatial statistics approaches to improve the efficiency of hyperparameter optimization. The spatial model used in our case study is a land price evaluation model in Mecklenburg County, North Carolina, USA. Our results demonstrate that the automated selection approach improves the model-level performance compared with linear regression, and the high-performance computing and spatial statistics approaches are of great help for accelerating and enhancing the selection of optimal neural networks for spatial modeling.