Skip to main content

Über dieses Buch

This book constitutes the refereed proceedings of the 8th International Conference on Geographic Information Science, GIScience 2014, held in Vienna, Austria in September 2014. The 23 full papers presented were carefully reviewed and selected from various submissions. The papers are organized in topical sections such as information visualization, spatial analysis, user-generated content, semantic models, wayfinding and navigation, spatial algorithms, and spatial relations.



Information Visualization

Map Schematization with Circular Arcs

We present an algorithm to compute schematic maps with circular arcs. Our algorithm iteratively replaces two consecutive arcs with a single arc to reduce the complexity of the output map and thus to increase its level of abstraction. Our main contribution is a method for replacing arcs that meet at high-degree vertices. This allows us to greatly reduce the output complexity, even for dense networks. We experimentally evaluate the effectiveness of our algorithm in three scenarios: territorial outlines, road networks, and metro maps. For the latter, we combine our approach with an algorithm to more evenly distribute stations. Our experiments show that our algorithm produces high-quality results for territorial outlines and metro maps. However, the lack of caricature (exaggeration of typical features) makes it less useful for road networks.
Thomas C. van Dijk, Arthur van Goethem, Jan-Henrik Haunert, Wouter Meulemans, Bettina Speckmann

Travel-Time Maps: Linear Cartograms with Fixed Vertex Locations

Linear cartograms visualize travel times between locations, usually by deforming the underlying map such that Euclidean distance corresponds to travel time. We introduce an alternative model, where the map and the locations remain fixed, but edges are drawn as sinusoid curves. Now the travel time over a road corresponds to the length of the curve. Of course the curves might intersect if not placed carefully. We study the corresponding algorithmic problem and show that suitable placements can be computed efficiently. However, the problem of placing as many curves as possible in an ideal, centered position is NP-hard. We introduce three heuristics to optimize the number of centered curves and show how to create animated visualizations.
Kevin Buchin, Arthur van Goethem, Michael Hoffmann, Marc van Kreveld, Bettina Speckmann

3D Network Spatialization: Does It Add Depth to 2D Representations of Semantic Proximity?

Spatialized views use visuo-spatial metaphors to facilitate sense-making from complex non-spatial databases. Spatialization typically includes the projection of a high-dimensional (non-spatial) data space onto a lower dimensional display space for visual data exploration. In comparison to 2D spatialized displays, 3D displays could potentially convey more information, as they employ all three available spatial display dimensions. In this study, we evaluate if this advantage exists and whether it outweighs the added cognitive, perceptual, and technological costs of 3D displays. In a controlled human-subjects experiment, we investigated how viewers identify document similarity in 3D network spatializations that depict news articles as points connected by links. Our quantitative findings suggest that similarity ratings for 3D network displays are similar to those obtained in a prior 2D study we conducted. With both types of displays, viewers mostly judged document similarity on the basis of metric distances along network links, as opposed to node counts or distance across the network links. However, node counts do affect similarity assessments with 3D displays more than with 2D displays. We also find no significant differences in similarity judgments whether 3D displays are presented monoscopically or stereoscopically. We conclude that any advantage of 3D displays in conveying more information than 2D displays does not necessarily outweigh their additional demands on cognitive, perceptual, and technological resources.
Sara Irina Fabrikant, Sara Maggi, Daniel R. Montello

Spatial Analysis

Uncertainty Analysis of Step-Selection Functions: The Effect of Model Parameters on Inferences about the Relationship between Animal Movement and the Environment

As spatio-temporal movement data is becoming more widely available for analysis in GIS and related areas, new methods to analyze them have been developed. A step-selection function (SSF) is a recently developed method used to quantify the effect of environmental factors on animal movement. This method is gaining traction as an important conservation tool; however there have been no studies that have investigated the uncertainty associated with subjective model decisions. In this research we used two types of animals – oilbirds and hyenas – to examine how systematically altering user decisions of model parameters influences the main outcome of an SSF, the coefficients that quantify the movement-environment relationship. We found that user decisions strongly influence the results of step-selection functions and any subsequent inferences about animal movement and environmental interactions. Differences were found between categories for every variable used in the analysis and the results presented here can help to clarify the sources of uncertainty in SSF model decisions.
Paul Holloway, Jennifer A. Miller

Logic Scoring of Preference and Spatial Multicriteria Evaluation for Urban Residential Land Use Analysis

The Logic Scoring of Preference (LSP) is a general multicriteria decision-making method with origins in soft computing and fuzzy reasoning. It allows the nonlinear aggregation of a large number of input criteria without the loss of significance typical for additive GIS-based MCE methods. The objective of this study is to integrate the LSP method with GIS and create LSP suitability maps for the land suitability analysis applied to real geospatial datasets for new urban residential development in the Metro Vancouver Region, Canada. Several factors influencing land use change were selected to construct the aggregation structure for the LSP-GIS method and implemented for decision-making purposes. This method allows simultaneity, replaceability and a range of other aggregators to match various evaluation objectives. The obtained results indicate that the LSP-MCE method provides refined evaluation of urban land suitability and therefore has a high potential for use in urban planning.
Kris Hatch, Suzana Dragićević, Jozo Dujmović

Spatial Weights: Constructing Weight-Compatible Exchange Matrices from Proximity Matrices

Exchange matrices represent spatial weights as symmetric probability distributions on pairs of regions, whose margins yield regional weights, generally well-specified and known in most contexts. This contribution proposes a mechanism for constructing exchange matrices, derived from quite general symmetric proximity matrices, in such a way that the margin of the exchange matrix coincides with the regional weights. Exchange matrices generate in turn diffusive squared Euclidean dissimilarities, measuring spatial remoteness between pairs of regions. Unweighted and weighted spatial frameworks are reviewed and compared, regarding in particular their impact on permutation and normal tests of spatial autocorrelation. Applications include tests of spatial autocorrelation with diagonal weights, factorial visualization of the network of regions, multivariate generalizations of Moran’s I, as well as “landscape clustering,” aimed at creating regional aggregates both spatially contiguous and endowed with similar features.
François Bavaud

Spatial Graphs Cost and Efficiency: Exploring Edges Competition by MCMC

Recent models for spatial networks have been built by determining graphs minimizing some functional F composed by two antagonist quantities. Although these quantities might differ from a model to another, methods used to solve these problems generally make use of simulated annealing or operations research methods, limiting themselves to the study of a single minimum and ignoring other close-to-optimal alternatives. This contribution considers the arguably promising framework where the functional F is composed by a graph cost and a graph efficiency, and the space of all possible graphs on n spatially fixed nodes is explored by MCMC. Covariance between edges occupancy can be derived from this exploration, revealing the presence of cooperative and competition regimes, further enlightening the nature of the alternatives to the locally optimal solution.
Guillaume Guex

User-Generated Content

Geosemantic Network-of-Interest Construction Using Social Media Data

An ever increasing amount of geospatial data generated by mobile devices and social media applications becomes available and presents us with applications and also research challenges. The scope of this work is to discover persistent and meaningful knowledge from user-generated location-based “stories” as reported by Twitter data. We propose a novel methodology that converts geocoded tweets into a mixed geosemantic network-of-interest (NOI). It does so by introducing a novel network construction algorithm on segmented input data based on discovered mobility types. The generated network layers are then combined into a single network. This segmentation addresses also the challenges imposed by noisy, low-sampling rate “social media” trajectories. An experimental evaluation assesses the quality of the algorithms by constructing networks for London and New York. The results show that this method is robust and provides accurate and interesting results that allow us to discover transportation hubs and critical transportation infrastructure.
Sophia Karagiorgou, Dieter Pfoser, Dimitrios Skoutas

Data Quality Assurance for Volunteered Geographic Information

The availability of technology and tools enables the public to participate in the collection, contribution, editing, and usage of geographic information, a domain previously reserved for mapping agencies or companies. The data of Volunteered Geographic Information (VGI) systems, such as OpenStreetMap (OSM), is based on the availability of technology and participation of individuals. However, this combination also implies quality issues related to the data: some of the contributed entities can be assigned to wrong or implausible classes, due to individual interpretation of the submitted data, or due to misunderstanding about available classes. In this paper we propose two methods to check the integrity of VGI data with respect to hierarchical consistency and classification plausibility. These methods are based on constraint checking and machine learning methods. They can be used to check the validity of data during contribution or at a later stage for collaborative manual or automatic data correction.
Ahmed Loai Ali, Falko Schmid

Semantics and Models

Re-Envisioning Data Description Using Peirce’s Pragmatics

Given the growth in geographical data production, and the various mandates to make sharing of data a priority, there is a pressing need to facilitate the appropriate uptake and reuse of geographical data. However, describing the meaning and quality of data and thus finding data to fit a specific need remain as open problems, despite much research on these themes over many years. We have strong metadata standards for describing facts about data, and ontologies to describe semantic relationships among data, but these do not yet provide a viable basis on which to describe and share data reliably. We contend that one reason for this is the highly contextual and situated nature of geographic data, something that current models do not capture well — and yet they could. We show in this paper that a reconceptualization of geographical information in terms of Peirce’s Pragmatics (specifically firstness, secondness and thirdness) can provide the necessary modeling power for representing situations of data use and data production, and for recognizing that we do not all see and understand in the same way. This in turn provides additional dimensions by which intentions and purpose can be brought into the representation of geographical data. Doing so does not solve all problems related to sharing meaning, but it gives us more to work with. Practically speaking, enlarging the focus from data model descriptions to descriptions of the pragmatics of the data — community, task, and domain semantics — allows us to describe the how, who, and why of data. These pragmatics offer a mechanism to differentiate between the perceived meanings of data as seen by different users, specifically in our examples herein between producers and consumers. Formally, we propose a generative graphical model for geographic data production through pragmatic description spaces and a pragmatic data description relation. As a simple demonstration of viability, we also show how this model can be used to learn knowledge about the community, the tasks undertaken, and even domain categories, from text descriptions of data and use-cases that are currently available. We show that the knowledge we gain can be used to improve our ability to find fit-for-purpose data.
Mark Gahegan, Benjamin Adams

Fields as a Generic Data Type for Big Spatial Data

This paper defines the Field data type for big spatial data. Most big spatial data sets provide information about properties of reality in continuous way, which leads to their representation as fields. We develop a generic data type for fields that can represent different types of spatiotemporal data, such as trajectories, time series, remote sensing and, climate data. To assess its power of generality, we show how to represent existing algebras for spatial data with the Fields data type. The paper also argues that array databases are the best support for processing big spatial data and shows how to use the Fields data type with array databases.
Gilberto Camara, Max J. Egenhofer, Karine Ferreira, Pedro Andrade, Gilberto Queiroz, Alber Sanchez, Jim Jones, Lubia Vinhas

Linked Data - A Paradigm Shift for Geographic Information Science

The Linked Data paradigm has made significant inroads into research and practice around spatial information and it is time to reflect on what this means for GIScience. Technically, Linked Data is just data in the simplest possible data model (that of triples), allowing for linking records or data sets anywhere across the web using controlled semantics. Conceptually, Linked Data offers radically new ways of thinking about, structuring, publishing, discovering, accessing, and integrating data. It is of particular novelty and value to the producers and users of geographic data, as these are commonly thought to require more complex data models. The paper explains the main innovations brought about by Linked Data and demonstrates them with examples. It concludes that many longstanding problems in GIScience have become approachable in novel ways, while new and more specific research challenges emerge.
Werner Kuhn, Tomi Kauppinen, Krzysztof Janowicz

An Ontology Design Pattern for Surface Water Features

Surface water is a primary concept of human experience but concepts are captured in cultures and languages in many different ways. Still, many commonalities exist due to the physical basis of many of the properties and categories. An abstract ontology of surface water features based only on those physical properties of landscape features has the best potential for serving as a foundational domain ontology for other more context-dependent ontologies. The Surface Water ontology design pattern was developed both for domain knowledge distillation and to serve as a conceptual building-block for more complex or specialized surface water ontologies. A fundamental distinction is made in this ontology between landscape features that act as containers (e.g., stream channels, basins) and the bodies of water (e.g., rivers, lakes) that occupy those containers. Concave (container) landforms semantics are specified in a Dry module and the semantics of contained bodies of water in a Wet module. The pattern is implemented in OWL, but Description Logic axioms and a detailed explanation is provided in this paper. The OWL ontology will be an important contribution to Semantic Web vocabulary for annotating surface water feature datasets. Also provided is a discussion of why there is a need to complement the pattern with other ontologies, especially the previously developed Surface Network pattern. Finally, the practical value of the pattern in semantic querying of surface water datasets is illustrated through an annotated geospatial dataset and sample queries using the classes of the Surface Water pattern.
Gaurav Sinha, David Mark, Dave Kolas, Dalia Varanka, Boleslo E. Romero, Chen-Chieh Feng, E. Lynn Usery, Joshua Liebermann, Alexandre Sorokine

Wayfinding and Navigation

An Indoor Navigation Ontology for Production Assets in a Production Environment

This article highlights an indoor navigation ontology for an indoor production environment. The ontology focuses on the movement of production assets in an indoor environment, to support autonomous navigation in the indoor space. Due to the fact that production environments have a different layout than ordinary indoor spaces, like buildings for office or residential use, an ontology focusing on indoor navigation looks different than ontologies in recent publications. Hence, rooms, corridors and doors to separate rooms and corridors are hardly present in an indoor production environment. Furthermore, indoor spaces for production purposes are likely to change in terms of physical layout and in terms of equipment location. The indoor navigation ontology highlighted in this paper utilizes an affordance based approach, which can be exploited for navigation purposes. A brief explanation of the routing methodology based on affordances is given in this paper, to justify the need for an indoor navigation ontology.
Johannes Scholz, Stefan Schabus

Wayfinding Decision Situations: A Conceptual Model and Evaluation

Humans engage in wayfinding many times a day. We try to find our way in urban environments when walking towards our work places or when visiting a city as tourists. In order to reach the targeted destination, we have to make a series of wayfinding decisions of varying complexity. Previous research has focused on classifying the complexity of these wayfinding decisions, primarily looking at the complexity of the decision point itself (e.g., the number of possible routes or branches). In this paper, we proceed one step further by incorporating the user, instructions, and environmental factors into a model that assesses the complexity of a wayfinding decision. We constructed and evaluated three models using data collected from an outdoor wayfinding study. Our results suggest that additional factors approximate the complexity of a wayfinding decision better than the simple model using only the number of branches as a criterion.
Ioannis Giannopoulos, Peter Kiefer, Martin Raubal, Kai-Florian Richter, Tyler Thrash

Understanding Information Requirements in “Text Only” Pedestrian Wayfinding Systems

Information that enables an urban pedestrian to get from A to B can come in many forms though maps are generally preferred. However, given the cognitive load associated with map reading, and the desire to make discrete use of mobile technologies, there is increasing interest in systems that deliver wayfinding information solely by means of georeferenced spoken utterances that essentially leave the user “technology free.” As a critical prior step, this paper examines the optimal delivery of such georeferenced text based instructions in anticipation of their spoken utterance. We identify the factors governing the content, location of instruction and frequency of delivery of text instructions such that a pedestrian can confidently follow a prescribed route, without reference to a map. We report on street level experiments in which pedestrians followed a sequence of text instructions delivered at key points along a set of routes. In examining instructions that are easy to follow, we compare landmark based instructions with street name based instructions. Results show that a landmark based approach is preferred because it is easier to assimilate (not because it is faster). Analysis also revealed that some degree of redundancy in the instructions is required in order to bring “comfort” to the user’s progress. There still remains the challenge of modeling the saliency of landmarks, knowing what is the most efficient set of instructions, and how to vary the frequency of instruction according to the complexity of the route. The paper concludes by identifying a set of design heuristics useful in the design of text based instructions for wayfinding.
William Mackaness, Phil Bartie, Candela Sanchez-Rodilla Espeso

Automatic Itinerary Reconstruction from Texts

This paper proposes an approach for the reconstruction of itineraries extracted from narrative texts. This approach is divided into two main tasks. The first extracts geographical information with natural language processing. Its outputs are annotations of so called expanded entities and expressions of displacement or perception from hiking descriptions. In order to reconstruct a plausible footprint of an itinerary described in the text, the second task uses the outputs of the first task to compute a minimum spanning tree.
Ludovic Moncla, Mauro Gaio, Sébastien Mustière

Integrating Sensing and Routing for Indoor Evacuation

Indoor evacuation systems are needed for rescue and safety management. A particular challenge is real-time evacuation route planning for the trapped people. In this paper, an integrated model is proposed for indoor evacuation used on mobile phones. With the purpose of employing real-time sensor data as references for evacuation route calculation, this paper makes an attempt to convert sensor systems to sensor graphs and associate these sensor graphs with route graph. Based on the integration of sensing and routing, sensor tracking and risk aware evacuation routes are generated dynamically for evacuees. Experiments of the proposed model are illustrated in the paper. The benefit of the integrated model could extend to hastily and secure indoor evacuation and it potentially presents an approach to correlate environmental information to geospatial information for indoor application.
Jing Wang, Stephan Winter, Daniel Langerenken, Haifeng Zhao

Spatial Algorithms

Significant Route Discovery: A Summary of Results

Given a spatial network and a collection of activities (e.g., pedestrian fatality reports, crime reports), Significant Route Discovery (SRD) finds all shortest paths in the spatial network where the concentration of activities is unusually high (i.e., statistically significant). SRD is important for societal applications in transportation safety, public safety, or public health such as finding routes with significant concentrations of accidents, crimes, or diseases. SRD is challenging because 1) there are a potentially large number of candidate routes (~1016) in a given dataset with millions of activities or road network nodes and 2) significance testing does not obey the monotonicity property. Previous work focused on finding circular areas of concentration, limiting its usefulness for finding significant linear routes on a network. SaTScan may miss many significant routes since a large fraction of the area bounded by circles for activities on a path will be empty. This paper proposes a novel algorithm for discovering statistically significant routes. To improve performance, the proposed algorithm features algorithmic refinements that prune unlikely paths and speeds up Monte Carlo simulation. We present a case study comparing the proposed statistically significant network-based analysis (i.e., shortest paths) to a statistically significant geometry-based analysis (e.g., circles) on pedestrian fatality data. Experimental results on real data show that the proposed algorithm, with our algorithmic refinements, yields substantial computational savings without reducing result quality.
Dev Oliver, Shashi Shekhar, Xun Zhou, Emre Eftelioglu, Michael R. Evans, Qiaodi Zhuang, James M. Kang, Renee Laubscher, Christopher Farah

Location Oblivious Privacy Protection for Group Nearest Neighbor Queries

Finding a convenient meeting point for a group is a common problem. For example, a group of users may want to meet at a restaurant that minimizes the group’s total travel distance. Such queries are called Group Nearest Neighbor (GNN) queries. Up to now, users have had to rely on an external party, typically a location service provider (LSP), for computing an optimal meeting point. This implies that users have to trust the LSP with their private locations. Existing techniques for private GNN queries either cannot resist sophisticated attacks or are computationally too expensive to be implemented on the popular platform of mobile phones. This paper proposes an algorithm to efficiently process private GNN queries. To achieve high efficiency we propose an approach that approximates a GNN with a high accuracy and is robust to attacks. Unlike methods based on obfuscation, our method does not require a user to provide an imprecise location and is in fact location oblivious. Our approach is based on a distributed secure sum protocol which requires only light weight computation. Our experimental results show that we provide a readily deployable solution for real life applications which can also be deployed for other geo-spatial queries and applications.
A. K. M. Mustafizur Rahman Khan, Tanzima Hashem, Egemen Tanin, Lars Kulik

Practical Approaches to Partially Guarding a Polyhedral Terrain

We study the problem of placing guard towers on a terrain such that the terrain can be seen from at least one tower. This problem is important in many applications, and has an extensive history in the literature (known as, e.g., multiple observer siting). In this paper, we consider the problem on polyhedral terrains, and we allow the guards to see only a fixed fraction of the terrain, rather than everything. We experimentally evaluate how the number of required guards relates to the fraction of the terrain that can be covered. In addition, we introduce the concept of dominated guards, which can be used to preprocess the potential guard locations and speed up the subsequent computations.
Frank Kammer, Maarten Löffler, Paul Mutser, Frank Staals

Spatial Relations

Oriented Regions for Linearly Conceptualized Features

The typical phenomena in geographic space are 2-dimensional or 3-dimensional in nature, yet people often conceptualize some of them as 1-dimensional entities embedded in a 2-dimensional space—rivers have widths and depths, and extent across the surface of the Earth, but for some tasks they are thought of as linear objects; likewise, roads as travel paths have widths as they wind through the landscape, but in some scenarios the extent is ignored and only connectivity between points along the path is considered. A critical property that makes these features special is the orientation that is attached (e.g., through the flow of the water or the traffic directions imposed by an authority). Contemporary spatial models capture such features either 1-dimensionally as networks of lines or directed lines, or 2-dimensionally simply as regions, each abstracting away one key property—in the case of the network the features’ extents and connections to neighboring areas, and in the case of regions their orientations. This paper introduces oriented regions as a model that preserves the key properties from both abstractions. Key properties of this approach are the sequences in which the boundaries of oriented regions interact, and the placement of objects with respect to the topological hull of a set of oriented regions. This model, dubbed hull+i, is based on topological hulls and the i-notation, a systematic method to capture boundary interactions between oriented regions, and provides a means for representing entire spatial scenes with an arbitrary number of objects, separations, and instances where ensembles of objects surround other objects.
Joshua A. Lewis, Max J. Egenhofer

RCC*-9 and CBM*

In this paper we introduce a new logical calculus of the Region Connection Calculus (RCC) family, RCC*-9. Based on nine topological relations, RCC*-9 is an extension of RCC-8 and models topological relations between multi-type geometric features: therefore, it is a calculus that goes beyond the modeling of regions as in RCC-8, being able to deal with lower dimensional features embedded in a given space, such as linear features embedded in the plane. Secondly, the paper presents a modified version of the Calculus-Based Method (CBM), a calculus for representing topological relations between spatial features. This modified version, called CBM*, is useful for defining a reasoning system, which was difficult to define for the original CBM. The two new calculi RCC*-9 and CBM* are introduced together because we can show that, even if with different formalisms, they can model the same topological configurations between spatial features and the same reasoning strategies can be applied to them.
Eliseo Clementini, Anthony G. Cohn


Weitere Informationen

Premium Partner