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.     

Efficiently implementable algebra for distributed in-network spatial analysis

Existing sensor network query processors (SNQPs) have demonstrated that in-network processing is an effective and efficient means of interacting with wireless sensor networks (WSNs) for data collection tasks. Inspired by these findings, this article investigates the question as to whether spatial analysis over WSNs can be built upon established distributed query processing techniques, but, here, emphasis is on the spatial aspects of sensed data, which are not adequately addressed in the existing SNQPs. By spatial analysis, we mean the ability to detect topological relationships between spatially referenced entities (e.g. whether mist intersects a vineyard or is disjoint from it) and to derive representations grounded on such relationships (e.g. the geometrical extent of that part of a vineyard that is covered by mist). To support the efficient representation, querying and manipulation of spatial data, we use an algebraic approach. We revisit a previously proposed centralized spatial algebra comprising a set of spatial data types and a comprehensive collection of operations. We have redefined and re-conceptualized the algebra for distributed evaluation and shown that it can be efficiently implemented for in-network execution. This article provides rigorous, formal definitions of the spatial data types, points, lines and regions, together with spatial-valued and topological operations over them. The article shows how the algebra can be used to characterize complex and expressive topological relationships between spatial entities and spatial phenomena that, due to their dynamic, evolving nature, cannot be represented a priori.     

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.     

An event-based spatiotemporal data model (ESTDM) for temporal analysis of geographical data

Abstract

Representations historically used within GIS assume a world that exists only in the present. Information contained within a spatial database may be added-to or modified over time, but a sense of change or dynamics through time is not maintained. This limitation of current GIS capabilities has recently received substantial attention, given the increasingly urgent need to better understand geographical processes and the cause-and-effect interrelationships between human activities and the environment. Models proposed so-far for the representation of spatiotemporal data are extensions of traditional raster and vector representations that can be seen as location- or feature-based, respectively, and are therefore best organized for performing either location-based or feature-based queries. Neither form is as well-suited for analysing overall temporal relationships of events and patterns of events throughout a geographical area as a temporally-based representation.

In the current paper, a new spatio-temporal data model is proposed that is based on time as its organizational basis, and is thereby intended to facilitate analysis of temporal relationships and patterns of change through time. This model is named the Event-based Spatio Temporal Data Model (ESTDM). It is shown that temporally-based queries relating to locations can be implemented in an efficient and conceptually straightforward manner using ESTDM by describing algorithms for three fundamental temporally-based retrieval tasks based on this model: (1) retrieving location(s) that changed to a given value at a given time, (2) retrieving location(s) that changed to a given value over a given temporal interval, and (3) calculation of the total area that has changed to a given value over a given temporal interval. An empirical comparison of the space efficiency of ESTDM and compressed and uncompressed forms of the ‘snapshot’ model is also given, showing that ESTDM is also a compact representation of spatio-temporal information.     

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.     

A unified approach for location-allocation analysis: integrating GIS,distributed computing and spatial optimization

Location-allocation modeling is an important area of research in spatial optimization and GIScience. A large number of analytical models for location-allocation analysis have been developed in the past 50 years to meet the requirements of different planning and spatial-analytic applications, ranging from the location of emergency response units (EMS) to warehouses and transportation hubs. Despite their great number, many location-allocation models are intrinsically linked to one another. A well-known example is the theoretical link between the classic p-median problem and coverage location problems. Recently, Lei and Church showed that a large number of classic and new location models can be posed as special case problems of a new modeling construct called the vector assignment ordered median problem (VAOMP). Lei and Church also reported extremely high computational complexity in optimally solving the best integer linear programming (ILP) formulation developed for the VAOMP even for medium-sized problems in certain cases.

In this article, we develop an efficient unified solver for location-allocation analysis based on the VAOMP model without using ILP solvers. Our aim is to develop a fast heuristic algorithm based on the Tabu Search (TS) meta-heuristic, and message passing interface (MPI) suitable for obtaining optimal or near-optimal solutions for the VAOMP in a real-time environment. The unified approach is particularly interesting from the perspective of GIScience and spatial decision support systems (DSS) as it makes it possible to solve a wide variety of location models in a unified manner in a GIS environment. Computational results show that the TS method can often obtain in seconds, solutions that are better than those obtained using the ILP-based approach in hours or a day.     

Spatial analysis of linguistic data with GIS functions

Abstract

During the 1980s techniques for analysis of geographical patterns have been refined to the point that they may be applied to data from many fields. Quantitative spatial analysis and existing functions available in geographical information systems (GIS) enable computerized implementations of these spatial analysis methods. This paper describes the application of quantitative spatial analysis and GIS functions to analysis of language data, using the extensive files of the Linguistic Atlas of the Middle and South Atlantic States (LAMSAS). A brief review of recent development of using quantitative and statistical methods for analysing linguistic data is also included.     

Measuring Global Spatial Autocorrelation with Data Reliability Information

Assessing spatial autocorrelation (SA) of statistical estimates such as means is a common practice in spatial analysis and statistics. Popular SA statistics implicitly assume that the reliability of the estimates is irrelevant. Users of these SA statistics also ignore the reliability of the estimates. Using empirical and simulated data, we demonstrate that current SA statistics tend to overestimate SA when errors of the estimates are not considered. We argue that when assessing SA of estimates with error, one is essentially comparing distributions in terms of their means and standard errors. Using the concept of the Bhattacharyya coefficient, we proposed the spatial Bhattacharyya coefficient (SBC) and suggested that it should be used to evaluate the SA of estimates together with their errors. A permutation test is proposed to evaluate its significance. We concluded that the SBC more accurately and robustly reflects the magnitude of SA than traditional SA measures by incorporating errors of estimates in the evaluation. Key Words: American Community Survey, Geary ratio, Moran’s I, permutation test, spatial Bhattacharyya coefficient.     

A comparative analysis of some two-dimensional orderings

Abstract

Many spatial analysis algorithms for cellular representations and data structures are based on an ordering of cells or objects to transform a two-dimensional problem to a one-dimensional one. Several orderings are available and their differing properties influence the performance of the data structures and algorithms. The relative merits of five orderings (row, row prime, Hilbert, Morton and Gray code) are assessed empirically for four paradigmatic geographical data-processing tasks in spatial analysis and data management. It is concluded that the Hilbert ordering deserves further investigation.     

Design and Usability of an Enhanced Geographic Information System for Exploration of Multivariate Health Statistics

Abstract

The multidimensional nature of many types of data in modern geography calls for creative and innovative approaches to their analysis. Statisticians have recently developed methods for exploring and visualizing large, multivariate datasets, but cartographers and geographers in general have only recently begun to integrate these methods for use with spatial and spatiotemporal datasets that are multivariate in character. This article will present an example of such an integration—an environment for visualization of health statistics—as a case study to demonstrate the philosophical and practical advantages of geovisualization systems for the exploration of complex spatiotemporal information. Emphasis is placed on the encouragement of creative thinking about geographic phenomena through the use of such data-rich graphical tools.

     

Fitzgerald: A Return to the Neighborhood and Its Contemporary Structural and Geographical Contexts

William Bunge's Fitzgerald: Portrait of a Revolution, initially published in 1971, is an enthralling verbal and visual account of the historical and geographical development of a one-square-mile neighborhood in Detroit. The original analysis of the Fitzgerald neighborhood was based on intensive field-based research conducted in a theoretical context of race and racism. The research reported here maintains that context but updates Fitzgerald's account of the neighborhood's built environment through a spatial analysis that uses parcel-by-parcel data generated in Google Earth and Google Street View instead of data collected in the field. Current spatial patterns of deterioration in the built environment are similar to those described in Fitzgerald, but positive sites are also apparent and often colocated with negative ones.     

Scale variance analysis coupled with Moran's I scalogram to identify hierarchy and characteristic scale

Scale variance is highly sensitive to multi-scale patterns of variables, which is advantageous in identifying spatial hierarchy and characteristic scale(s). However, the significance of peak(s) in scale variance cannot be statistically tested, and different spatial patterns may be obtained when different zoning systems are used to calculate scale variance. To address these two problems, this study compared the scale levels with peaks in scale variance and the scale levels at which there were breaks in the nature of spatial autocorrelation as identified by shifts in Moran's I scalogram. The estimates for three simulated landscapes showed that accordance between scale levels identified employing the two methods can be used to evaluate the significance of peaks in scale variance and choose a more reasonable zoning system. The approach of scale variance analysis coupled with Moran's I scalogram was also applied to the Xilin River Basin of Inner Mongolia, China. The most vital characteristic scale (64 × 32 km) identified for the growing-season net ecosystem productivity (NEP) of the basin was validated by other spatial pattern analysis methods such as semi-variogram, Moran's I correlogram, and wavelet variance analyses, and the directionality of the chosen zoning systems was found to be similar to the orientation of actual dominant vegetation type patches. The results demonstrate that Moran's I scalogram can be used to improve the interpretation of the results of scale variance analysis and increase the reliability of scale variance analysis for landscapes having a repetitive patch pattern or gradient variation and that the proposed approach is suitable for identifying the hierarchy and the characteristic scales of patterns or processes. In summary, this study used a simple approach to solve two problems in scale variance analysis, thereby improving the methodology and enhancing the theoretical basis of multi-scale analysis.     

Active Learning Strategies and Assessment in World Geography Classes

Abstract

Active learning strategies include a variety of methods, such as inquiry and discovery, in which students are actively engaged in the learning process. This article describes several strategies that can be used in secondary-or college-level world geography courses. The goal of these activities is to foster development of a spatial perspective in students through frequent analysis and interpretation of spatial data. Detailed examples of one particular technique, the “atlas warmup”, are included. Active approaches supplement expository teaching of standards-based geography concepts and current geographic issues. Assessment of the impact of these methods reveals the need for ongoing guided practice in the use of these skills.     

Design of a spatial data structure using the relational normal forms

Abstract

In previous work, a relational data structure aimed at the exchange of spatial data between systems was developed. As this data structure was relational it was of first normal form, but compliance with the higher normal forms was not investigated. Recently, a new procedural method for composing fully normalized data structures from the basic data fields has been developed by H. C. Smith, as an alternative to the process of non-loss decomposition which is difficult to understand. Smith's method has been applied to data fields required to store points, lines and polygons in a chain-node spatial data model. When geographic domain, coverage layer and map are also considered, the procedure naturally leads to a catalogue model, needed for the exchange of spatial data. Although the method produces a fully normalized data structure, it is not as easy to identify which normal forms are responsible for the ultimate arrangement of the data fields into relations, but the benefits of these criteria for data base development also apply to spatial data structures and related ancillary data.     

空间视角下的能源—经济—环境关系研究进展与展望

在全球气候变化和国际地缘政治复杂的背景之下,地理学的空间视角为能源—经济—环境关系研究提供了新的研究思路。论文通过梳理、评述能源—经济、能源—环境以及能源—经济—环境关系研究文献发现：① 能源—经济关系研究出现“空间转向”趋势,区位特征被用于解释能源—经济关系的空间异质性;② 能源—环境关系研究多关注能源污染及政策的空间效应,出现了能源景观研究等新研究话题;③ 能源—经济—环境关系研究刚刚兴起,出现了因果关系实证、耦合协调度评价、多目标规划预测3种研究思路;④ 当前研究存在实证分析高度同质化、空间差异机制解释不足、可再生能源相关研究较少等不足之处。据此,论文尝试构建了空间视角下能源—经济—环境(3E)关系研究基础框架,并基于中国研究现状提出未来的研究展望,即完善理论框架建设、加强可再生能源研究以及开展碳减排目标下的能源—经济—环境系统模拟预测,从而为中国碳达峰、碳中和目标的实现提供理论与实证支撑。     

Logical data modelling for geographical applications

Abstract.

A formal, yet practical, GeoRelational Data Model (GRDM) is presented for the logical database design phase of the development of spatial information systems. Geographic applications are viewed in the context of information systems development. The generic needs of modelling spatial data are analyzed; it is concluded that they are not served satisfactorily by existing data models, so specifications of modelling tools for spatial application design are given. GRDM provides a set of representational constructs (relations and layers for the logical schema; virtual layers, object classes and spatial constraints for the user views) on top of well-established models. It constitutes part of a full, easily automated application design methodology. Extensive examples demonstrate the relevance, and ease-of-use of the platform-independent GRDM.     

Integrating GIS and spatial data analysis: problems and possibilities

Abstract

This article is an agreed summary of a workshop held in Sheffield between 18-20 March 1991. The focus here is on three of the themes of the workshop: the mutual benefits of closer links between geographical information systems (GIS) and the methods of spatial data analysis (SDA); the specific areas of SDA that should be linked with GIS; how the linkage should be made in practice. Directions for future research are also reviewed. The emphasis throughout is on statistical SDA and principally from the perspective of human rather than physical geography.     

Observational Work for Children

Abstract

Geographic information systems (GIS) are computer-based tools for geographic data analysis and spatial visualization. They have become one of the information and communications technologies for education at all levels. This article reviews the current status of GIS in schools, analyzes the requirements of a GIS-based learning environment from constructivist perspectives, and discusses the major issues in the design of a constructivist GIS-based learning environment based on experience from the development of World Explorer, a GIS-based learning environment that provides a theme-oriented data and information base, supports multiple representations and multiple linkages of information, and facilitates interactive learning and knowledge construction.     

Design of a view-based DSS for location planning

Abstract.

The traditional approach in DSS falls short of providing a highly interactive problem solving environment for planning. Often, cumbersome procedures are required to implement optional plans and obtain feedback information. In dynamic graphic systems, the user is able to view different linked graphic representations (e.g., spatial or statistical graphs) of statistical data and interact (e.g., selecting items) with these graphics. In this paper we describe the design of a DSS for planning facility locations, which uses principles of dynamic graphics to achieve a highly interactive problem solving environment. As in dynamic graphic systems, the user interacts with the DSS through active and linked views. However, where views in dynamic graphics are different representations of a given dataset, the views in the DSS are active data structures describing the facility system to be planned from different perspectives. The declarative and procedural forms of knowledge involved are identified by a logical analysis of planning problems. A frame-based formalism is proposed to represent the knowledge contained in the views. The main advantage of this view-based approach is that it offers the user a highly flexible and interactive environment for performing ‘what-if’ analyses.