Integration of spatial data in vector and raster formats in a geographic information system environment

This paper examines the common methods for converting spatial data sets between vector and raster formats and presents the results of extensive benchmark testing of these procedures. The tests performed are unique in this field since: (1) they used both synthetic and real test data sets; (2) they measured conversion quality, accuracy and efficiency, not just how fast the procedure operated; and (3) they were conducted in a generic geographic information system (GIS) environment without the aid of specialized computer hardware. The results show that the best overall techniques are the ones which take advantage of spatial relationships inherent in the data sets. These were the Scan Line algorithm for vector to raster conversions and the Boundary Linking algorithm for raster to vector conversions.     

Data structures for three-dimensional spatial information systems in geology

Abstract

The accumulation of geological information in digital form, due to modern exploration methods, has introduced the possibility of applying geographical information system technology to the field of geology. To achieve the benefits in information management and in data analysis and interpretation, however, it will be necessary to develop spatial models and associated data structures which are specifically designed for working in three dimensions. Some progress in this direction has already been demonstrated, with the application of octree spatial subdivision techniques to the storage of uniform volume elements representing mineral properties. By imposing octree tessellations on more precisely-defined geometric data, such as triangulated surfaces and polygon line segments, it may now be possible to combine efficient spatial addressing with topologically-coded boundary representations of geological strata. The development of storage schemes capable of representing such geological boundary models at different scales poses a particular problem, a possible solution to which may be by means of hierarchical classification of the vertices of triangulated surfaces according to shape contribution.     

Discovering environmental data: metadatabases,network information resource tools and the GENIE system

Abstract

The existence of global computer networks in conjunction with various computer based tools offers the GIS community the possibility of identifying existing spatial data in a faster and more complete way. Using such tools could help the GIS community reduce the high costs of data collection. This paper focuses on the discovery of environmental data using metadatabases and network information resource tools and includes comments on some of the limitations of these computer based tools. The article will conclude by describing how the system developed by the GENIE project attempts to overcome some of these limitations.     

Representing geographical objects with scale‐induced indeterminate boundaries: A neural network‐based data model

The degree of uncertainty of many geographical objects has long been known to be in intimate relation with the scale of its observation and representation. Yet, the explicit consideration of scaling operations when modeling uncertainty is rarely found. In this study, a neural network‐based data model was investigated for representing geographical objects with scale‐induced indeterminate boundaries. Two types of neural units, combined with two types of activation function, comprise the processing core of the model, where the activation function can model either hard or soft transition zones. The construction of complex fuzzy regions, as well as lines and points, is discussed and illustrated with examples. It is shown how the level of detail that is apparent in the boundary at a given scale can be controlled through the degree of smoothness of each activation function. Several issues about the practical implementation of the model are discussed and indications on how to perform complex overlay operations of fuzzy maps provided. The model was illustrated through an example of representing multi‐resolution, sub‐pixel maps that are typically derived from remote sensing techniques.     

Finding shortest paths on real road networks: the case for A*

The problem of identifying the shortest path along a road network is a fundamental problem in network analysis, ranging from route guidance in a navigation system to solving spatial allocation problems. Since this type of problem is solved so frequently, it is important to craft an approach that is as efficient as possible. Based upon past research, it is generally accepted that several efficient implementations of the Dijkstra algorithm are the fastest at optimally solving the ‘one‐to‐one’ shortest path problem (Cherkassky et al. 1996 Cherkassky, B. V., Goldberg, A. V. and Radzik, T. 1996. Shortest paths algorithms: theory and experimental evaluation.. Mathematical Programming: Series A and B, 73: 129–174. [Crossref], [Web of Science ®] , [Google Scholar]). We show that the most efficient state‐of‐the‐art implementations of Dijkstra can be improved by taking advantage of network properties associated with GIS‐sourced data. The results of this paper, derived from tests of different algorithmic approaches on real road networks, will be extremely valuable for application developers and researchers in the GIS community.     

Ranking spaces for predicting human movement in an urban environment

A city can be topologically represented as a connectivity graph, consisting of nodes representing individual spaces and links if the corresponding spaces are intersected. It turns out in the space syntax literature that some defined topological metrics can capture human movement rates in individual spaces. In other words, the topological metrics are significantly correlated to human movement rates, and individual spaces can be ranked by the metrics for predicting human movement. However, this correlation has never been well justified. In this paper, we study the same issue by applying the weighted PageRank algorithm to the connectivity graph or space–space topology for ranking the individual spaces, and find surprisingly that: (1) the PageRank scores are better correlated to human movement rates than the space syntax metrics, and (2) the underlying space–space topology demonstrates small world and scale free properties. The findings provide a novel justification as to why space syntax, or topological analysis in general, can be used to predict human movement. We further conjecture that this kind of analysis is no more than predicting a drunkard's walking on a small world and scale free network.     

Modeling uncertainty of moving objects on road networks via space–time prisms

Moving objects produce trajectories, which are typically observed in a finite sample of time‐stamped locations. Between sample points, we are uncertain about the moving objects's location. When we assume extra information about an object, for instance, a (possibly location‐dependent) speed limit, we can use space–time prisms to model the uncertainty of an object's location.

Until now, space–time prisms have been studied for unconstrained movement in the 2D plane. In this paper, we study space–time prisms for objects that are constrained to travel on a road network. Movement on a road network can be viewed as essentially one‐dimensional. We describe the geometry of a space–time prism on a road network and give an algorithm to compute and visualize space–time prisms. For experiments and illustration, we have implemented this algorithm in MATHEMATICA.

Furthermore, we study the alibi query, which asks whether two moving objects could have possibly met or not. This comes down to deciding if the chains of space–time prisms produced by these moving objects intersect. We give an efficient algorithm to answer the alibi query for moving objects on a road network. This algorithm also determines where and when two moving objects may have met.     

Constructing personalized transportation networks in multi-state supernetworks: a heuristic approach

An integrated view encompassing the networks for public and private transport modes as well as the activity programs of travelers is essential for accessibility analysis. In earlier research, the multi-state supernetwork has been put forward by the authors as a suitable technique to model the system in such an integrated fashion. An essential part of a supernetwork involving multi-modal and multi-activity is the personalized transportation network, which is an under-researched topic in the academic community. This article attempts to develop a heuristic approach to construct personalized transportation networks for an individual's activity program. In this approach, the personalized network consists of two types of network extractions from the original transportation system: public transport network and private vehicle network. Three examples are presented to illustrate that the public transport network and private vehicle network can represent an individual's attributes and be applied in large-scale applications for analyzing the synchronization of land-use and transportation systems.     

Integration of linear and areal hierarchies for continuous multi-scale representation of road networks

Spatial data can be represented at different scales, and this leads to the issue of multi-scale spatial representation. Multi-scale spatial representation has been widely applied to online mapping products (e.g., Google Maps and Yahoo Maps). However, in most current products, multi-scale representation can only be achieved through a series of maps at fixed scales, resulting in a discontinuity (i.e., with jumps) in the transformation between scales and a mismatch between the available scales and users' desired scales. Therefore, it is very desirable to achieve smoothly continuous multi-scale spatial representations. This article describes an integrated approach to build a hierarchical structure of a road network for continuous multi-scale representation purposes, especially continuous selective omission of roads in a network. In this hierarchical structure, the linear and areal hierarchies are constructed, respectively, using two existing approaches for the linear and areal patterns in a road network. Continuous multi-scale representation of a road network can be achieved by searching in these hierarchies. This approach is validated by applying it to two study areas, and the results are evaluated by both quantitative analysis with two measures (i.e., similarity and average connectivity) and visual inspection. Experimental results show that this integrated approach performs better than existing approaches, especially in terms of preservation of connectivity and patterns of a road network. With this approach, efficient and continuous multi-scale selective omission of road networks becomes feasible.     

Statistics-based outlier detection for wireless sensor networks

Wireless sensor network (WSN) applications require efficient, accurate and timely data analysis in order to facilitate (near) real-time critical decision-making and situation awareness. Accurate analysis and decision-making relies on the quality of WSN data as well as on the additional information and context. Raw observations collected from sensor nodes, however, may have low data quality and reliability due to limited WSN resources and harsh deployment environments. This article addresses the quality of WSN data focusing on outlier detection. These are defined as observations that do not conform to the expected behaviour of the data. The developed methodology is based on time-series analysis and geostatistics. Experiments with a real data set from the Swiss Alps showed that the developed methodology accurately detected outliers in WSN data taking advantage of their spatial and temporal correlations. It is concluded that the incorporation of tools for outlier detection in WSNs can be based on current statistical methodology. This provides a usable and important tool in a novel scientific field.