Local interpolation using a distributed parallel supercomputer

Abstract

Large spatial interpolation problems present significant computational challenges even for the fastest workstations. In this paper we demonstrate how parallel processing can be used to reduce computation times to levels that are suitable for interactive interpolation analyses of large spatial databases. Though the approach developed in this paper can be used with a wide variety of interpolation algorithms, we specifically contrast the results obtained from a global ‘brute force’ inverse–distance weighted interpolation algorithm with those obtained using a much more efficient local approach. The parallel versions of both implementations are superior to their sequential counterparts. However, the local version of the parallel algorithm provides the best overall performance.     

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.     

Fuzzy reasoning in the development of geographical information systems FRSIS: a prototype soil information system with fuzzy retrieval capabilities

Abstract

The characteristics of a soil information system based on the fuzzy relational database model as defined by Zemankova-Leech and Kandel are presented. The proposed system maintains all the advantages of the more conventional relational implementations but enhances them in two ways: (1) the system can cope with incomplete or even imprecise data; and (2) the users are allowed to express their subjective view of the stored data. The retrieval and processing of data approximately resemble the way that humans think and reason. The INGRES relational database management system was used for the implementation of the system.     

Parallel identification and filling of depressions in raster digital elevation models

With the increasing sizes of digital elevation models (DEMs), there is a growing need to design parallel schemes for existing sequential algorithms that identify and fill depressions in raster DEMs. The Priority-Flood algorithm is the fastest sequential algorithm in the literature for depression identification and filling of raster DEMs, but it has had no parallel implementation since it was proposed approximately a decade ago. A parallel Priority-Flood algorithm based on the fastest sequential variant is proposed in this study. The algorithm partitions a DEM into stripes, processes each stripe using the sequential variant in many rounds, and progressively identifies more slope cells that are misidentified as depression cells in previous rounds. Both Open Multi-Processing (OpenMP)- and Message Passing Interface (MPI)-based implementations are presented. The speed-up ratios of the OpenMP-based implementation over the sequential algorithm are greater than four for all tested DEMs with eight computing threads. The mean speed-up ratio of our MPI-based implementation is greater than eight over TauDEM, which is a widely used MPI-based library for hydrologic information extraction. The speed-up ratios of our MPI-based implementation generally become larger with more computing nodes. This study shows that the Priority-Flood algorithm can be implemented in parallel, which makes it an ideal algorithm for depression identification and filling on both single computers and computer clusters.     

Leveraging parallel spatio-temporal computing for crime analysis in large datasets: analyzing trends in near-repeat phenomenon of crime in cities

ABSTRACT

Crime often clusters in space and time. Near-repeat patterns improve understanding of crime communicability and their space–time interactions. Near-repeat analysis requires extensive computing resources for the assessment of statistical significance of space–time interactions. A computationally intensive Monte Carlo simulation-based approach is used to evaluate the statistical significance of the space-time patterns underlying near-repeat events. Currently available software for identifying near-repeat patterns is not scalable for large crime datasets. In this paper, we show how parallel spatial programming can help to leverage spatio-temporal simulation-based analysis in large datasets. A parallel near-repeat calculator was developed and a set of experiments were conducted to compare the newly developed software with an existing implementation, assess the performance gain due to parallel computation, test the scalability of the software to handle large crime datasets and assess the utility of the new software for real-world crime data analysis. Our experimental results suggest that, efficiently designed parallel algorithms that leverage high-performance computing along with performance optimization techniques could be used to develop software that are scalable with large datasets and could provide solutions for computationally intensive statistical simulation-based approaches in crime analysis.     

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.     

UK-based terrorists' antecedent behavior: A spatial and temporal analysis

Background and purposeTerrorism is a real and present danger. The build-up to an attack includes planning, travel, and reconnaissance which necessarily require the offender to move through their environment. Whilst research has examined patterns of terrorist attack locations, with a few exceptions (e.g. Rossmo & Harries, 2011), it has not examined the spatial behavior of the terrorists themselves. In this paper, we investigate whether the spatial mobility patterns of terrorists resemble those of criminals (and the wider population) and if these change in the run up to their attacks.MethodUsing mobile phone data records for the ringleaders of four different UK-based terrorist plots in the months leading up to their attacks, we examine the frequency with which terrorists visit different locations, how far they travel from key anchor points such as their home, the distance between sequential cell-site hits and how their range of movement varies as the planned time to attack approaches.ConclusionsLike the wider population (and criminals), the sample of terrorists examined exhibited predictable patterns of spatial behavior. Most movements were close to their home location or safe house, and they visited a relatively small number of locations most of the time. Disaggregating these patterns over time provided mixed evidence regarding the way in which their spatial activity changed as the time to the planned attack approached. The findings are interpreted in terms of how they inform criminological understanding of the spatial behavior of terrorists, and the implications for law enforcement.     

Parallel polygon line shading: the quest for more computational power from an existing GIS algorithm

Abstract

Utilising the powerful resources of a parallel computer has become a technique available to the GIS software engineer for increasing the performance of such complex software systems. This paper discusses the effectiveness of both automatic and manual parallelising techniques with a view to making an assessment as to whether the inherent sequential structure of GIS software is a detrimental factor inhibiting the use of such techniques. With the aid of the Scan Line Fill (SLF) algorithm in GIMMS, it has been shown that whilst automated parallelization has no merits in this case, a significant performance benefit can be achieved with algorithm redesign at the macro level to exploit the natural geometric parallelism inherent within the algorithm. However, the results illustrate that the full potential of this approach will not be appreciated until the I/O bottleneck is completely overcome, as opposed to merely avoided.     

Comparison of existing methods for building triangular irregular network,models of terrain from grid digital elevation models

Abstract

Triangulated irregular networks (TINs) are increasingly popular for their efficiency in data storage and their ability to accommodate irregularly spaced elevation points for many applications of geographical information systems. This paper reviews and evaluates various methods for extracting TINs from dense digital elevation models (DEMs) on a sample DEM. Both structural and statistical comparisons show that the methods perform with different rates of success in different settings. Users of DEM to TIN conversion methods should be aware of the strengths and weaknesses of the methods in addition to their own purposes before conducting the conversion.     

Geostatistical modelling of spatial uncertainty using p -field simulation with conditional probability fields

This paper presents a variant of p-field simulation that allows generation of spatial realizations through sampling of a set of conditional probability distribution functions (ccdf) by sets of probability values, called p-fields. Whereas in the common implementation of the algorithm the p-fields are nonconditional realizations of random functions with uniform marginal distributions, they are here conditional to 0.5 probability values at data locations, which entails a preferential sampling of the central part of the ccdf around these locations. The approach is illustrated using a randomly sampled (200 observations of the NIR channel) SPOT scene of a semi-deciduous tropical forest. Results indicate that the use of conditional probability fields improves the reproduction of statistics such as histogram and semivariogram, while yielding more accurate predictions of reflectance values than the common p-field implementation or the more CPU-intensive sequential indicator simulation. Pixel values are then classified as forest or savannah depending on whether the simulated reflectance value exceeds a given threshold value. In this case study, the proposed approach leads to a more precise and accurate prediction of the size of contiguous areas covered by savannah than the two other simulation algorithms.     

Parallelizing visibility computations on triangulated terrains

Abstract

In this paper we address the problem of computing visibility information on digital terrain models in parallel. We propose a parallel algorithm for computing the visible region of an observation point located on the terrain. The algorithm is based on a sequential triangle-sorting visibility approach proposed by De Floriani et al. (1989). Static and dynamic parallelization strategies, both in terms of partitioning criteria and scheduling policies, are discussed. The different parallelization strategies are implemented on an MIMD multicomputer and evaluated through experimental results.     

Research Paper. The predictive use of GIS to model property valuations

Abstract

GIS is a technology which is ideally suited to analysis of the market values of properties, since such values are based upon spatial comparisons as well as individual property attributes. Great Britain now has a new mechanism of local taxation, the council tax, which is based upon the capital values of properties. Central to the implementation of this tax has been the potentially controversial assignment of properties to valuation ‘bands’. This paper posits that a geographical model embedded within a GIS provides an alternative means of devising credible capital values, and anticipates some of the prospects for the use of GIS in local revenue-raising.     

GIS and remote sensing integration for environmental applications

Abstract

The combined use of remotely-sensed images and vector GIS data has received considerable interest in recent years. This review article discusses the historical move towards closer integration of remote sensing and GIS technologies and the requirements of integrated software systems to enable remotely-sensed data to be combined with vector datasets for maximum effect. The benefits of integration to users of both GIS and remote sensing for environmental applications are reviewed and some thoughts are given on terminology and future directions in this field.     

Incorporating spatial association into statistical classifiers: local pattern-based prior tuning

ABSTRACT

This paper proposes a new classification method for spatial data by adjusting prior class probabilities according to local spatial patterns. First, the proposed method uses a classical statistical classifier to model training data. Second, the prior class probabilities are estimated according to the local spatial pattern and the classifier for each unseen object is adapted using the estimated prior probability. Finally, each unseen object is classified using its adapted classifier. Because the new method can be coupled with both generative and discriminant statistical classifiers, it performs generally more accurately than other methods for a variety of different spatial datasets. Experimental results show that this method has a lower prediction error than statistical classifiers that take no spatial information into account. Moreover, in the experiments, the new method also outperforms spatial auto-logistic regression and Markov random field-based methods when an appropriate estimate of local prior class distribution is used.     

Mining spatiotemporal association patterns from complex geographic phenomena

ABSTRACT

Spatiotemporal association pattern mining can discover interesting interdependent relationships among various types of geospatial data. However, existing mining methods for spatiotemporal association patterns usually model geographic phenomena as simple spatiotemporal point events. Therefore, they cannot be applied to complex geographic phenomena, which continuously change their properties, shapes or locations, such as storms and air pollution. The most salient feature of such complex geographic phenomena is the geographic dynamic. To fully reveal dynamic characteristics of complex geographic phenomena and discover their associated factors, this research proposes a novel complex event-based spatiotemporal association pattern mining framework. First, a complex geographic event was hierarchically modeled and represented by a new data structure named directed spatiotemporal routes. Then, sequence mining technique was applied to discover the spatiotemporal spread pattern of the complex geographic events. An adaptive spatiotemporal episode pattern mining algorithm was proposed to discover the candidate driving factors for the occurrence of complex geographic events. Finally, the proposed approach was evaluated by analyzing the air pollution in the region of Beijing-Tianjin-Hebei. The experimental results showed that the proposed approach can well address the geographic dynamic of complex geographic phenomena, such as the spatial spreading pattern and spatiotemporal interaction with candidate driving factors.     

Guest editorial

The past decade has witnessed extensive development of measures that examine characteristics of spatial subsets (local spaces) defined with respect to a complete data set (global space). Such procedures have evolved independently in fields such as geography, GIS, cartography, remote sensing, and landscape ecology. Collectively, we label these procedures as local spatial methods. We focus on those methods that share a common goal of identifying subsets whose characteristics are statistically ‘significant’ in some way. We propose the concept of local spatial statistical analysis (LoSSA) both as an integrative structure for existing methods and as a framework that facilitates the development of new local and global statistics. By formalizing what is involved when a particular local statistic is used, LoSSA helps to reveal the key features and limitations of the procedure. These include a consideration of the nature of the spatial subsets, their spatial relationship to the complete data set, and the relationship between a given global statistic and the corresponding local statistics computed for the data set.     

Modelling the temporal element in land information systems

Abstract

This paper considers the use of a modern programming language (Modula-2) to develop a data model for a lot-based land information system. The emphasis is on the importance of maintaining the history of the lots, and a data model is developed which incorporates the history of each lot.     

Parallel processing on heterogeneous networks for GIS applications

Abstract

The use of network-based parallel computing is gaining an increasing popularity for different reasons. Its exploitation depends on the availability of simple but effective methodologies to parallelize applications, and the availability of portable and efficient communication libraries to develop parallel programs. These two items are necessary to obtain performance advantages, and to ensure software portability and reusability. In this paper we present our experience in parallelizing, in a systematic way, a class of Geographical Information Systems applications. We discuss the use of two well-known communication libraries (PVM and Linda). Performance results are also reported.     

Technical Note The b-function and variable stream buffer mapping: a note on ‘A GIS method for riparian water quality buffer generation’

Abstract

Mapping variable stream buffers in a vector environment in which buffer width values are delineated often yields inaccurate results. Possible vector solutions are either ineffective or inefficient, An alternate raster approach is presented here in which a buffer effectiveness-achievement function (b-function) is introduced to map desirable buffer zones at an individual cell level based upon areal differentiations in physical and ecological conditions. The implementation of b-function is made feasible by a GIS procedure devised in this article. This tested method can be extended to a variety of variable buffer studies, such as visual buffers, noise buffers, greenways, and urban natural buffers.

‘A robe can never be made of the fur from one fox's axillae’ (A Chinese idiom).