4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)
Share your fundamental techniques for spatial processing.
1 November 2022
Seattle, Washington USA
Part of 30th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2022)
A spatial gem is a brief description of fundamental approach for processing spatial data. At the workshops, participants worked together to edit all the accepted submissions for clarity and utility, with the goal of creating a reference archive of spatial techniques.
Papers from Spatial Gems 2019
Papers from Spatial Gems 2020
Papers from Spatial Gems 2021
Papers from Spatial Gems 2022
Spatial Gems 2022
Object Delineation in Satellite Images (PDF)
Zhuocheng Shang - University of California, Riverside (Riverside, CA USA)
Ahmed Eldawy - University of California, Riverside (Riverside, CA USA)
Abstract: Machine learning is being widely applied to analyze satellite data with problems such as classification and feature detection. Unlike traditional image processing algorithms, geospatial applications need to convert the detected objects from a raster form to a geospatial vector form to further analyze it. This gem delivers a simple and light-weight algorithm for delineating the pixels that are marked by ML algorithms to extract geospatial objects from satellite images. The proposed algorithm is exact and users can further apply simplification and approximation based on the application needs.
@inproceedings{Shang2022objectdelineation,
author = {Zhuocheng Shang and Ahmed Eldawy },
title = {Object Delineation in Satellite Images},
booktitle ={4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)},
organization = {ACM},
year = {2022},
location = {Seattle, WA USA}}
Implementing Simulation of Simplicity for Geometric Degeneracies (PDF)
W. Randolph Franklin - Rensselaer Polytechnic Institute (Troy, NY USA)
Salles Viana Gomes de Magalhães -- Universidade Federal de Viçosa (Viçosa MG Brazil)
We describe how to implement Simulation of Simplicity (SoS). SoS removes geometric degeneracies in point-in-polygon queries, polyhedron intersection, map overlay, and other 2D and 3D geometric and spatial algorithms by determining the effect of adding non-Archimedian infinitesimals of different orders to the coordinates. Then it modifies the geometric predicates to emulate that, and evaluates them in the usual arithmetic.
A geometric degeneracy is a coincidence, such as a vertex of one polygon on an edge of another polygon, that would have probability approaching zero if the objects were distributed i.i.d. uniformly. However, in real data, they can occur often. Especially in 3D, there are too many types of degeneracies to reliably enumerate. But, if they are not handled, then predicates evaluate wrong, and the output topology may be wrong.
We describe the theory of SoS, and how several algorithms and programs were successfully modified, including volume of the union of many cubes, point location in a 3D mesh, and intersecting 3D meshes.
@inproceedings{Franklin2022simulationofsimplicty,
author = { W. Randolph Franklin and Salles Viana Gomes de Magalhães },
title = { Implementing Simulation of Simplicity for Geometric Degeneracies},
booktitle ={4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)},
organization = {ACM},
year = {2022},
location = {Seattle, WA USA}}
Probabilistic Counting in Uncertain Spatial Databases using Generating Functions (PDF)
Andreas Zufle -- Emory University (Atlanta, GA USA)
Many applications using spatial data require counting the number of spatial objects within a region. In cases where the locations of objects are uncertain, this count becomes random variable. This spatial gem gives an efficient solution for computing the probability mass function of this random variable, that is computing for each integer $n$ the probability of having exactly $n$ objects within the region.
@inproceedings{ Zufle2022probabilisticcounting,
author = { Andreas Zufle },
title = { Probabilistic Counting in Uncertain Spatial Databases using Generating Functions},
booktitle ={4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)},
organization = {ACM},
year = {2022},
location = {Seattle, WA USA}}
Statistics for All Walks on a Lattice Graph (PDF)
John Krumm – Microsoft Research (Redmond, WA USA)
Trajectory data from a moving entity may be handicapped by the temporal gaps between location measurements. We can make inferences about the locations visited during the gaps by postulating all possible paths between pairs of temporally adjacent measurements. These paths are modeled as walks on a spatially discrete grid, represented as a lattice graph. From the collection of possible walks, we can compute statistics about the possible location visits between the measurements, including the probabilities of visiting discrete grid cells and for how long. The paper shows how to compute these statistics, which we share at https://github.com/jckrumm-microsoft/WalksOnLatticeGraph.
@inproceedings{Krumm2022statisticswalks,
author = {John Krumm},
title = { Statistics for All Walks on a Lattice Graph},
booktitle ={4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)},
organization = {ACM},
year = {2022},
location = {Seattle, WA USA}}
Online Heatmap Generation with Both High and Low Weights (PDF)
Yan Y. Liu -- Oak Ridge National Laboratory (Oak Ridge, TN USA)
Melissa Allen-Dumas-- Oak Ridge National Laboratory (Oak Ridge, TN USA)
Heatmap is a common geovisualization method that interpolates and visualizes a set of point observations on a map surface. Most of online web mapping libraries implement a one-pass heatmap algorithm using HTML5 canvas or WebGL for efficient heatmap generation. However, such implementation applies additive operations that accumulate the rendering of point weights on the map surface grid, making it inappropriate for visualizations that require the highlighting of both low and high weights. We introduce hilomap, an online heatmap algorithm that highlights surface areas where points with both low and high trends are located. An HTML5 Canvas-based reference implementation on OpenLayers is presented and evaluated.
@inproceedings{Liu2022onlineheatmap,
author = {Yan Y. Liu and Melissa Allen-Dumas},
title = {Online Heatmap Generation with Both High and Low Weights},
booktitle ={4th ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2022)},
organization = {ACM},
year = {2022},
location = {Seattle, WA USA}}
Spatial Gems 2021
Gaussian Process for Trajectories (PDF)
Kien Nguyen - University of Southern California (Los Angeles, CA USA)
John Krumm - Microsoft Research (Redmond, WA USA)
Cyrus Shahabi - University of Southern California (Los Angeles, CA USA)
Abstract: The Gaussian process is a powerful and flexible technique for interpolating spatiotemporal data, especially with its ability to capture complex trends and uncertainty from the input signal. This chapter describes Gaussian processes as an interpolation technique for geospatial trajectories. A Gaussian process models measurements of a trajectory as coming from a multidimensional Gaussian, and it produces for each timestamp a Gaussian distribution as a prediction. We discuss elements that need to be considered when applying Gaussian process to trajectories, common choices for those elements, and provide a concrete example of implementing a Gaussian process.
@inproceedings{Nguyen2021gaussianprocess,
author = {Kien Nguyen and John Krumm and Cyrus Shahabi},
title = {Gaussian Process for Trajectories},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Mean Chord Length of a Square (PDF)
John Krumm - Microsoft Research (Redmond, WA USA)
Abstract: This paper derives the mean chord length of a square. For a circle, a chord is a straight line segment connecting any two points on the perimeter. The same is true for a square. The paper shows that for a square of dimensions l × l, the mean chord length is ρl, where ρ ≈ 0.7098, assuming a certain reasonable distribution of chords. The mean chord length is useful for choosing the dimensions of cells in a square grid for discretizing spatial trajectories.
@inproceedings{Krumm2021Meanchordsquare,
author = { John Krumm },
title = {Mean Chord Length of a Square},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Graph Sampling for Map Comparison (PDF)
Jordi Aguilar - Universitat Politècnica de Catalunya (Barcelona, Spain)
Kevin Buchin - TU Eindhoven (Eindhoven, Netherlands)
Maike Buchin - Ruhr University Bochum (Bochum, Germany)
Erfan Hosseini Sereshgi - Tulane University (New Orleans, Louisiana USA)
Rodrigo I. Silveira - Universitat Politècnica de Catalunya (Barcelona, Spain)
Carola Wenk - Tulane University (New Orleans, Louisiana USA)
Abstract: Comparing two road maps is a basic operation that arises in a variety of situations. A map comparison method that is commonly used, mainly in the context of comparing reconstructed maps to ground truth maps, is based on graph sampling. The essential idea is to first compute a set of point samples on each map, and then to match pairs of samples—one from each map—in a one-to-one fashion. For deciding whether two samples can be matched, different criteria can be used. The total number of matched pairs gives a measure of how similar the maps are.
Since the work of Biagioni and Eriksson [1, 2], graph sampling methods have become widely used. However, there are different ways to implement each of the steps, which can lead to significant differences in the results. This means that conclusions drawn from different studies that seemingly use the same comparison method, cannot necessarily be compared.
In this work we present a unified approach to graph sampling for map comparison. In particular, we point out the importance of the sampling method (GEO vs. TOPO) and that of the matching definition, discussing the main options used precisely, and proposing better alternatives for both key steps in details. Furthermore, we provide a code base and an interactive visualization tool to set a standard for future evaluations in the field of map construction and map comparison.
@inproceedings{Agular2021Graphsampling,
author = { Jordi Aguilar and Kevin Buchin and Maike Buchin and Erfan Hosseini Sereshgi, Rodribo I. Silveria, Carola Wenk },
title = {Graph Sampling for Map Comparison},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Fast 3-D Euclidean Connected Components (PDF)
W. Randolph Franklin - Rensselaer Polytechnic Institute (Troy, New York USA)
Salles Viana Gomes de Magalhães - Universidade Federal de Viçosa (Viçosa, Brazil)
Eric N. Landis - University of Maine (Orono, Maine USA)
We present an efficient algorithm and implementation for computing the connected components
within a 3-D cube of voxels, also known as the Euclidean union-find problem. There may be over 109
voxels. The components may be 8-connected or 26-connected. Computing connected components has
applications ranging from material failure in concrete under increasing stress to electrical conductivity
in complex metal objects to elasticity in 3D printed parts. One key to efficiency is representing voxels
by 1-D runs of adjacent voxels. We also compute each component’s surface area. As a special case,
2-D connected components of images may easily be computed.
@inproceedings{Franklin2021Connected,
author = { W. Randolph Franklin and Salles Viana Gomes de Viçosa and Eric N. Landis },
title = {Fast 3-D Euclidean Connected Components},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Spatial-to-Image Coordinate Transformations (PDF)
Samantha T. Arundel - United States Geological Survey (Rolla, Missouri USA)
Trenton P. Morgan - United States Geological Survey (Rolla, Missouri USA)
Philip T. Thiem - United States Geological Survey (Rolla, Missouri USA)
Wenwen Li - Arizona State University (Tempe, Arizona USA)
Sizhe Wang - Arizona State University (Tempe, Arizona USA)
This article describes techniques to transform spatial coordinates to image coordinates when creating
training data for machine learning applications under various scenarios. Although simple challenges
arise just related to the different coordinate system origins, they become complex when offsetting
(translating), rotating, and scaling geographic features. This article highlights an illustrated explanation
of the fundamental spatial to image coordinate transformation, as well as automated techniques
for resolving transformation needs.
@inproceedings{Arundel2021Transforms,
author = { Samantha T. Arundel and Trenton P. Morgan and Philip T. Thiem and Wenwen Li and Sizhe Wang },
title = {Spatial-to-Image Coordinate Transformations},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Multi-scalar Window Aggregation for Rasters (PDF)
Anne M. Denton - North Dakota State University (Fargo, North Dakota USA)
Aggregates over sliding windows are an important part of many analyzes over raster images, including
computation of basic statistic quantities, regression analysis, fractal dimensions, and topographic
analysis. For those analyses, the most appropriate window size is not always obvious a priori and
the window sizes may be very large. An algorithm is presented for aggregating windows iteratively
with a performance that is logarithmic in the window size. The main limitations of the algorithm
are that aggregation functions must be additive in the sense that performing aggregations based on
prior aggregates must be possible, and that window sizes are powers of two. When those assumptions
can be met, the algorithm can be used in a variety of contexts that would otherwise either require a
substantial reduction of resolution or take excessive computation time.
@inproceedings{Denton2021Window,
author = { Anne M. Denton },
title = {Multi-scalar Window Aggregation for Rasters},
booktitle ={3rd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2021)},
organization = {ACM},
year = {2021},
location = {Beijing, China}}
Spatial Gems 2020
A Practical Network Layout Planning System Using Geospatial Data (PDF, slides)
Chun-Ting Wu – Microsoft (Taipei, Taiwan)
Jason Hong – Microsoft (Bellevue, Washington, USA)
Seshagiri Cherukuri – Microsoft (Bellevue, Washington, USA)
Wan Jia Kun Zhu – Microsoft (Bellevue, Washington, USA)
Yi Zhang – Microsoft (Bellevue, Washington, USA)
Chi-Wei Kao – Microsoft (Taipei, Taiwan)
Abstract: Network construction cost optimization is a classic scenario for Steiner Minimum Tree (SMT) problem and a well known NP-hard question. In this paper, we demonstrate a practical planning system for calculating network construction cost, allowing users to generate a viable solution by simply selecting entities from the map interactively. One difference from the original SMT problem is that instead of connecting entities directly, constructing network along exiting road network is more cost-efficient. In this system, for simplicity, we adopt the 2-approximation algorithm for Steiner Tinimum Tree to solve this problem and showed how we integrate roads data into the result to fit real-world scenario.
@inproceedings{wu2020layout,
author = { Chun-Ting Wu and Jason Hong and Seshagiri Cherukuri and Wan Jia Kun Zhu and Yi Zhang and Chi-Wei Kao},
title = {A practical network layout planning system using geospatial data},
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
The Brownian Bridge for Space-Time Interpolation (PDF, slides)
John Krumm - Microsoft Research (Redmond, Washington, USA)
Abstract: The Brownian bridge gives a principled method for interpolating in space and time between two timestamped points. It expresses the uncertainty of the interpolated location as a time-dependent Gaussian distribution. This chapter explains the Brownian bridge, shows how to integrate it to get probabilities over space and time, and demonstrates how to fit a Brownian bridge to spatiotemporal data. The explanations of integrating and fitting use a running example with numerical values as an aid to debugging. A larger example demonstrates the fitting of a Brownian bridge model to long trajectories of bald eagles.
@inproceedings{krumm2020brownianbridge,
author = {John Krumm},
title = {The Brownian bridge for space-time interpolation},
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
A Scalable In-Memory Solution for Real-Time K Nearest Search on Road Network (PDF, slides)
Hao Wu - GrabTaxi Holdings (Singapore)
Minglei Su - GrabTaxi Holdings (Singapore)
Thanh Dat Le - GrabTaxi Holdings (Singapore)
Nuo Xu - GrabTaxi Holdings (Singapore)
Guanfeng Wang - GrabTaxi Holdings (Singapore)
Mihai Stroe - GrabTaxi Holdings (Singapore)
Abstract: K Nearest Neighbour (KNN) has always been a popular research topic across different industries. For ride-hailing companies, locating the K nearest drivers with respect to a point of interest (POI) is one of the fundamental features for reliable and efficient location-based service. In this scenario, continuously fast-moving drivers on road network and finding the K nearest drivers in routing distance are two major challenges. This paper presents Pharos, which supports massive frequent location updates and real-time KNN query in routing distance with a decentralized and scalable in-memory storage. Pharos adopts Adaptive Radix Trees to store the indexes between drivers and road segments. KNN search in Pharos is implemented based on Incremental Network Expansion and drivers are retrieved from the nearest road segments during this isochrone expansion. Pharos currently runs in our production environment and efficiently supports real-time location updates of millions of drivers on the road with thousands of K nearest search requests simultaneously.
@inproceedings{wu2020knearestroad,
author = { Hao Wu and Minglei Su and Thanh Dat Le and Nuo Xu and Guanfeng Wang and Mihai Stroe },
title = {A scalable in-memory solution for real-time K nearest search on road network},
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing (PDF, slides)
Marcelo Menezes - Universidade Federal de Viçosa (Viçosa, Minas Gerais, Brazil)
Salles V. G. de Magalhães - Universidade Federal de Viçosa (Viçosa, Minas Gerais, Brazil)
Matheus Aguilar - Universidade Federal de Viçosa (Viçosa, Minas Gerais, Brazil)
W. Randolph Franklin - Rensselaer Polytechnic Institute (Troy, New York, USA)
Bruno Coelho - Universidade Federal de Viçosa (Viçosa, Minas Gerais, Brazil)
Abstract: This paper presents a technique to use GPUs to accelerate the computation of 3D geometric predicates. A common predicate is computing the orientation of four 3D points, which is a subproblem in applications such as intersecting two 3D meshes. Since the higher level application may require billions of evaluations, efficiency is important. Accuracy is required since floating roundoff errors can cause topological impossibilities. One solution is to compute with rational numbers, but that is difficult to implement on a GPU because rationals' sizes vary. Our solution is to compute on the GPU with interval arithmetic, but fall back to using rationals on the CPU if the interval computed on the GPU includes the origin; i.e., its sign is unknown. Our experiment with a dataset of hard rock mining drill holes show that this fallback to the CPU is rarely necessary; so that our technique gave a 17 times speedup compared to a sequential implementation.
@inproceedings{ Menezes2020GPU3D,
author = { Marcelo Menezes and Salles V. G. de Magalhães and Matheus Aguilar and W. Randolph Fra and Bruno Coelho },
title = { Employing GPUs to accelerate exact geometric predicates for 3D geospatial processing },
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
Using Segment Fraction For Road-Network Locations (PDF)
Yuanyuan Pao – Lyft (San Francisco, California, USA)
Abstract: Locations are often specified as (latitude, longitude) coordinates, which require specific distance methods based on spherical geometry to process. If the locations lie on a road network, then operations such as nearby search, speed computation, location prediction, or interpolation will require further processing with the road geometry. We propose augmenting the location representation with road segment ID and segment fraction for road-based locations and argue that, in doing so, commonly-used operations are greatly simplified and correspond to intuitive formulas.
@inproceedings{ pao2020segmentfraction,
author = { Yuanyuan Pao },
title = { Using segment fraction for road-network locations },
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
Flexible Computation of Multidimensional Histograms (PDF, slides)
Samriddhi Singla - University of California Riverside (Riverside, California, USA)
Ahmed Eldawy - University of California Riverside (Riverside, California, USA)
Abstract: Histograms are a popular method to understand spatial data distribution and help facilitate query optimization, approximate query processing, and load balancing. The most common computation method for histograms requires two passes over the data, first to compute the data domain and then to compute the histogram values. This gem presents an alternative method that can compute an approximate histogram in one pass over the data, which makes it more suitable for incremental computation and streaming applications where two passes over the data are not possible. It can also be more efficient if reading the input data is costly, e.g., requires decompression. The key algorithm that makes the one-scan algorithm possible is for merging two non-aligned histograms.
@inproceedings{ singla2020histograms,
author = { Samriddhi Singla and Ahmed Eldawy },
title = { Flexible computation of multidimensional histograms },
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
TINET: Triangulated Irregular Networks Evolving in Time (PDF, slides)
Goce Trajcevski - Iowa State University (Ames, Iowa, USA)
Prabin Giri - Iowa State University (Ames, Iowa, USA)
Xu Teng - Iowa State University (Ames, Iowa, USA)
Hooman Hashemi- Iowa State University (Ames, Iowa, USA)
Abstract: Triangulated Irregular Networks (TIN) are popular structure in Geographic Information Systems (GIS) software, used for representing surfaces via discrete triangular facets. Often times, the 3D vertices are obtained from: (i) a collection of 2D points, corresponding to physical locations; and (ii) a ``mass'' value corresponding to the third dimension, representing a magnitude of a measurement in each location. The organization of the 2D points for representing TINs is based on Delaunay triangulation, a well known concept from Computational Geometry. In practice, however, measurements in each location are also taken in multiple discrete time instants, thereby inducing a location-bound time series. Combining the values from the locations in discrete time instants, in turn, creates a setting of evolving TINs. This work describes TINET (TINs Evolving in Time) -- a methodology for comparing surfaces represented by TINs in different time instants. Such feature is essential for reasoning about aggregated properties of the evolution of a special phenomena, such as examining the similarity/distance between rainfall or CO2 distribution at different times.
@inproceedings{trajcevski2020TINET,
author = { Goce Trajcevski and Prabin Giri and Xu Teng and Hooman Hashemi },
title = { TINET: Triangulated irregular networks evolving in time },
booktitle ={2nd ACM SIGSPATIAL International Workshop on Spatial Gems (SpatialGems 2020)},
organization = {ACM},
year = {2020},
location = {Seattle, Washington USA}
}
Spatial Gems 2019
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}
}