The Spatial Gems workshop was held on 5 November 2019 as part of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2019).
A spatial gem is a brief description of fundamental approach for processing spatial data. At the workshop, participants worked together to edit all the accepted submissions for clarity and utility, with the goal of creating a reference archive of spatial techniques.
These are the papers from the 2019 Spatial Gems workshop.
Heat Map Segmentation (PDF)
Gil Wolff - Amazon (Bellevue, Washington USA)
Abstract: Many geospatial datasets can be represented as a heat map, such as rainfall, population density, terrain elevation, and others. These heat maps tend to form clusters of high density areas among a background of low density areas. This gem presents an automatic way to detect such clusters, and segment the heat map into areas. Experiments are conducted for two datasets which correlate to population density and show that the segmentation aligns with metropolitan areas and is stable to the choice of dataset. The segmentation described in this gem can potentially aid geospatial algorithms by supplying a smart divide-and-conquer strategy, such that the algorithm does not need to run for the entire Earth, but rather there can be a fine-grained model for each area.
@inproceedings{wolff2019heatmap,
author = {Gil Wolf},
title = {Heat map segmentation},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Online Location Trajectory Compression (PDF)
ABM Musa - Amazon (Bellevue, Washington USA)
James Biagioni - Carmera (Seattle, Washington USA)
Jakob Eriksson - University of Illinois at Chicago (Chicago, Illinois USA)
Abstract: This paper presents a system for online GPS tracking, where a device reports its location in near real-time to a central server over a cellular uplink. Here, a user can specify the error and the delay bound, and the system optimizes the uplink usage. Experiments show that this system reduces the data usage 20 times or more compared to the status quo while providing improved guarantees and flexibility.
@inproceedings{musa2019compression,
author = {ABM Musa and James Biagioni and Jakob Eriksson},
title = {Online location trajectory compression},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Spatial Data Generators (PDF) (Best Paper Award)
Tin Vu - University of California, Riverside (Riverside, California USA)
Sara Migliorini - University of Verona (Verona, Italy)
Ahmed Eldawy - University of California, Riverside (Riverside, California USA)
Alberto Bulussi - University of Verona (Verona, Italy)
Abstract: This gem describes a standard method for generating synthetic spatial data that can be used in benchmarking and scalability tests. The goal is to improve the reproducibility and increase the trust in experiments on synthetic data by using standard widely acceptable dataset distributions. In addition, this article describes how to assign a unique identifier to each synthetic dataset that can be shared in papers for reproducibility of results. Finally, this gem provides a supplementary material that gives a reference implementation for all the provided distributions.
@inproceedings{vu2019generators,
author = {Tin Vu and Sara Migliorini and Ahmed Eldawy and Alberto Bulussi},
title = {Spatial data generators},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Complete and Sufficient Spatial Domination of Multidimensional Rectangles (PDF)
Tobias Emrich - Harman International (Munich, Germany)
Hans-Peter Kriegel - Ludwig Maximilian University of Munich (Munich, Germany)
Andreas Züfle - George Mason University (Fairfax, Virginia USA)
Peer Kröger - Ludwig Maximilian University of Munich (Munich, Germany)
Matthias Renz - Christian-Albrechts-Universität zu Kiel (Kiel, Germany)
Abstract: Rectangles are used to approximate objects, or sets of objects, in a plethora of applications, systems and index structures. Many tasks, such as nearest neighbor search and similarity ranking, require to decide if objects in one rectangle A may/must/must not be closer to objects in a second rectangle $B$, than objects in a third rectangle R. To decide this relation of ``Spatial Domination'' it can be shown that using minimum and maximum distances it is often impossible to detect spatial domination. This spatial gem provides a necessary and sufficient decision criterion for spatial domination that can be computed efficiently even in higher dimensional space. In addition, this spatial gem provides an example, pseudocode and an implementation in Python.
@inproceedings{emrich2019rectangles,
author = {Tobias Emrich and Hans-Peter Kriegel and Andreas Z\"ufle and Peer Kr\"oger and Matthias Renz},
title = {Complete and sufficient spatial domination of multidimensional rectangles},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Minimal Representations of Polygons and Polyhedra (PDF)
W. Randolph Franklin - Rensselaer Polytechnic Institute (Troy, New York USA)
Salles Viana Gomes de Magalhaes - Universidade Federal de Viçosa (Viçosa MG Brazil)
Abstract: We present several simple representations of polygon and polyhedra that permit the efficient parallel computation of area and volume. They are particularly useful for computing the areas of the nonempty intersections between pairs of faces in two overlapping planar graphs in GIS, or the volumes of nonempty intersections between pairs of tetrahedra in two overlapping triangulations of a polyhedron in CAD. Both applications have been implemented on multicore Intel Xeons and tested on large datasets. The representations store the minimal types of information required for computation, and never need to store edge loops and face shells, or even most adjacency relations. The representations are sets of tuples or small fixed-size sets, and can be processed in parallel with map-reduce operations.
@inproceedings{franklin2019minimal,
author = {W. Randolph Franklin and Salles Viana Gomes de Magalh\~aes},
title = {Minimal representations of polygons and polyhedra},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Simplification of Indoor Space Footprints (PDF)
Joon-Seok Kim - George Mason University (Fairfax, Virginia USA)
Carola Wenk - Tulane University (New Orleans, Lousianna USA)
Abstract: Simplification is one of the fundamental operations used in geoinformation science (GIS) to reduce size or representation complexity of geometric objects. Although different simplification methods can be applied depending on one’s purpose, a simplification that many applications employ is designed to preserve their spatial properties after simplification. This article addresses one of the 2D simplification methods, especially working well on human-made structures such as 2D footprints of buildings and indoor spaces. The method simplifies polygons in an iterative manner. The simplification is segmentwise and takes account of intrusion, extrusion, offset, and corner portions of 2D structures preserving its dominant frame.
@inproceedings{kim2019indoor,
author = {Joon-Seok Kim and Carola Wenk},
title = {Simplification of indoor space footprints},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}
Speed Distribution from Normally Distributed Location Measurements (PDF)
John Krumm - Microsoft Research (Redmond, Washington USA)
Abract: This article describes how to compute a probability distribution of speed from a pair of uncertain location measurements taken at different times. When location measurements are uncertain, the method shows how to propagate this uncertainty to the resulting speed computation. We assume the location measurements are normally distributed. While the resulting speed distribution is not normal, it can be approximated as normal. The article derives the speed distribution, verifies it with a simulation, and gives a numerical example for debugging.
@inproceedings{krumm2019speed,
author = {John Krumm},
title = {Speed distribution from normally distributed location measurements},
booktitle ={1st ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2019)},
organization = {ACM},
year = {2019},
location = {Chicago, Illinois USA}
}