Accepted Full Paper Abstracts
Emre Eftelioglu, Yan Li, Xun Tang, James M. Kang, Christopher Farah and Shashi Shekhar.
Mining Network Hotspots with Holes: A Summary of Results
Abstract: Given a spatial network and a collection of activities (e.g. crime locations), the problem of Mining Network Hotspots with Holes (MNHH) finds network hotspots with doughnut shaped spatial footprint, where the concentration of activities is unusually high (e.g. statistically significant). MNHH is important for societal applications such as criminology, where it may focus the efforts of officials to identify a crime source. MNHH is challenging because of the large number of candidates and the high computational cost of statistical significance test. Previous work focused either on geometry based hotspots (e.g. circular, ring-shaped) on Euclidean space or connected subgraphs (e.g. shortest path), limiting the ability to detect statistically significant hotspots with holes on a spatial network. This paper proposes a novel Network Hotspot with Hole Generator (NHHG) algorithm to detect network hotspots with holes. The proposed algorithm features refinements that improve the performance of a naive approach. Case studies on real crime datasets confirm the superiority of NHHG over previous approaches. Experimental results on real data show that the proposed approach yields substantial computational savings without reducing result quality.
Cici Alexander, Lars Arge, Peder Klith Bøcher, Morten Revsbæk, Brody Sandel, Jens-Christian Svenning, Constantinos Tsirogiannis and Jungwoo Yang. Computing River Floods Using Massive Terrain Data
Abstract: Many times in history, river floods have resulted in huge catastrophes. To reduce the negative outcome of such floods, it is important to predict their extent before they happen. For this reason, specialists use algorithms that model river floods on digital terrains datasets. Nowadays, massive terrain datasets have become widely available. As flood modeling is an important part for a wide range of professions, it is crucial to process such datasets fast even with standard computers. Yet, these datasets can be several times larger than the main memory of a standard computer. Unfortunately, existing flood-modeling algorithms cannot handle this situation efficiently. Hence they have to sacrifice output quality for time performance, or vice versa.
In this paper, we present a novel algorithm that, unlike any previous approach, can both provide high-quality river flood modeling and handle massive terrain data efficiently. More than that, we redesigned an existing popular flood-modeling method (approved by European Union and used by authorities in Denmark) so that it can efficiently process huge terrain datasets. Given a raster terrain G and a subset of its cells representing a river network, both algorithms estimate for each cell in G the height that the river should rise for the cell to get flooded. Based on our design, both algorithms can process terrain datasets that are much larger than the main memory of a computer. For an input raster that consists of N cells, and which is so large that it can only be stored in the hard disk, each of the described algorithms can produce its output with only O(sort(N)) transfers of data blocks between the disk and the main memory. Here sort(N) denotes the minimum number of data transfers needed for sorting N elements stored on disk. We implemented both algorithms, and compared their output with data acquired from a real flood event. We show that our new algorithm models the real event quite accurately, more accurately than the existing popular method. We evaluated the efficiency of the algorithms in practice by conducting experiments on massive datasets. Each algorithm could process a dataset of 268 GB size on a computer with only 22 GB working main memory (twelve times smaller than the dataset itself) in at most 31 hours.
Kwangsoo Yang. Distance-Constrained k Spatial Sub-Networks: A Summary of Results
Abstract: Given a graph and a set of spatial events, the goal of Distance-Constrained k Spatial Sub-Networks (DCSSN) problem is to ﬁnd k sub-networks that meet a distance constraint and maximize the number of spatial events covered by the sub-networks. The DCSSN problem is important for many societal applications, such as police patrol assignment and emergency response assignment. The problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the distance constraint. This paper proposes a novel approach for ﬁnding k sub-networks that maximize the coverage of spatial events under the distance constraint. Experiments and a case study using Chicago crime datasets demonstrate that the proposed algorithm outperforms baseline approaches and reduces the computational cost to create a DCSSN.
Benjamin Niedermann and Martin Nöllenburg. An Algorithmic Framework for Labeling Road Maps
Abstract: Given an unlabeled road map, we consider, from an algorithmic perspective, the cartographic problem of placing non-overlapping road labels embedded in the roads. We first decompose the road network into logically coherent road sections, i.e., parts of roads between two junctions. Based on this decomposition, we present and implement a new and versatile framework for placing labels in road maps such that the number of labeled road sections is maximized. In an experimental evaluation with road maps of 11 major cities we show that our proposed labeling algorithm is both fast in practice and that it reaches near-optimal solution quality, where optimal solutions are obtained by mixed-integer linear programming. In direct comparison, our algorithm consistently outperforms the standard OpenStreetMap renderer Mapnik.
Takeshi Shirabe. On Distortion of Raster-based Least-cost Corridors
Abstract: Given a grid of cells each having a cost value, a variant of the least-cost path problem seeks a corridor—represented by a swath of cells rather than a sequence of cells—connecting two terminuses such that its total accumulated cost is minimized. While it is widely known that raster-based least-cost paths are subject to three types of distortion, i.e. deviation, distortion, and proximity, little is known about potential distortion of their corridor counterparts. This paper examines a raster model of the least-cost corridor problem and analyses its solution in terms of each type of distortion. It is found that raster-based least-cost corridors, too, are subject to all three types of distortion but in different ways: elongation distortion is always persistent, deviation distortion can be substantially reduced, and proximity distortion can be essentially eliminated.
Benjamin Adams and Mark Gahegan. Exploratory chronotopic data analysis
Jan-Henrik Haunert and Wouter Meulemans. Partitioning Polygons via Graph Augmentation
Qinghan Liang, Silvia Nittel and Torsten Hahmann. From Data Streams to Fields: Extending Stream Data Models with Field Data Types
Abstract: With ubiquitous live sensors and sensor networks, increasingly large numbers of individual sensors are deployed in physical space. Sensor data streams are a fundamentally novel mechanism to create and deliver observations to information systems, enabling us to represent spatiotemporal continuous phenomena such as radiation accidents, pollen distributions, or toxic plumes almost as instantaneously as they happen in the real world. While data stream engines (DSE) are available to process high-throughput updates, DSE support for phenomena that are continuous in both space and time is not available. This places the burden of handling any tasks related to the integration of potentially very large sets of concurrent sensor streams into higher-level abstractions on the user. In this paper, we propose a formal extension to stream data model languages based on the concept of fields to support high-level abstractions of continuous ST phenomena that are known to the DSE, and therefore, can be supported through queries and processing optimization. The proposed field data types are formalized in a data model language independent way using second order signatures. We formalize both the set of supported field types are as well as the embedding into stream data model languages.
Dipto Sarkar, Renée Sieber and Raja Sengupta. GIScience considerations in spatial social networks
Peter Kiefer, Ioannis Giannopoulos, Andrew Duchowski and Martin Raubal. Measuring Cognitive Load for Map Tasks through Pupil Diameter
Abstract: In this paper we use pupil diameter as an indicator for measuring cognitive load for six different tasks on common web maps. Two eye tracking data sets were collected for different basemaps (37 participants and 1,328 trials in total). We found significant differences in mean pupil diameter between tasks, indicating low cognitive load for free exploration, medium cognitive load for search, polygon comparison, line following, and high cognitive load for route planning and focused search. Pupil diameter also changed over time within trials which can be interpreted as an increase in cognitive load for search and focused search, and a decrease for line following. Such results can be used for the adaptation of maps and geovisualizations based on their users’ cognitive load.
Joshua Lewis and Max Egenhofer. Point Partitions: A Qualitative Representation for Region-Based Spatial Scenes in R^2
Joseph Tuccillo and Barbara Buttenfield. Model-Based Clustering of Social Vulnerability to Urban Extreme Heat Events
Xiaoxiao Liu and Stefania Bertazzon. Fine Scale Spatio-temporal Modelling of Urban Air Pollution
Arthur van Goethem, Marc Van Kreveld and Bettina Speckmann. Circles in the water: towards island group labeling
Jiaoli Chen and Shih-Lung Shaw. Representing the Spatial Extent of Places based on Flickr Photos with a Representativeness-Weighted Kernel Density Estimation
Matt Duckham, Marc Van Kreveld, Ross Purves, Bettina Speckmann, Yaguang Tao, Kevin Verbeek and Jo Wood. Modeling Checkpoint-based Movement with the Earth Mover’s Distance
Carson Farmer and Carsten Keßler. Hierarchical Prism Trees for Scalable Time Geographic Analysis
Tuhin Paul, Kevin Stanley, Nathaniel Osgood, Scott Bell and Nazeem Muhajarine. Scaling Behavior of Human Mobility Distributions
Krzysztof Janowicz, Yingjie Hu, Grant McKenzie, Song Gao, Blake Regalia, Gengchen Mai, Rui Zhu, Benjamin Adams and Kerry Taylor. Moon Landing or Safari? A Study of Systematic Errors and their Causes in Geographic Linked Data
Ashwin Shashidharan, Derek Berkel, Ranga Raju Vatsavai and Ross Meentemeyer. pFUTURES: A Parallel Framework for Cellular Automaton Based Urban Growth Models
Chris Allen, Thomas Hervey, Werner Kuhn, Sara Lafia, Daniel W. Phillips and Behzad Vahedi. Exploring the Notion of Spatial Lenses
Abstract: We explore the idea of spatial lenses as pieces of software interpreting data sets in a particular spatial view of an environment. The lenses serve to prepare the data sets for subsequent analysis in that view. Examples include a network lens to view places in a literary text, or a eld lens to interpret pharmacy sales in terms of seasonal allergy risks. The theory underlying these lenses is that of core concepts of spatial information, but here we exploit how these concepts enhance the usability of data rather than that of systems. Spatial lenses also supply transformations between multiple views of an environment, for example, between eld and object views. They lift these transformations from the level of data format conversions to that of understanding an environment in multiple ways. In software engineering terms, spatial lenses are defined by constructors, generating instances of core concept representations from spatial data sets. Deployed as web services or libraries, spatial lenses would make larger varieties of data sets amenable to mapping and spatial analysis, compared to today’s situation, where le formats determine and limit what one can do. To illustrate and evaluate the idea of spatial lenses, we present a set of experimental lenses, implemented in a variety of languages, and test them with a variety of data sets, some of them non-spatial.