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

Spatial Gems 2020

 

A Practical Network Layout Planning System Using Geospatial Data (PDFslides)

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}
}

©2020 by Spatial Gems