Polygon Simplification for the Efficient Approximate Analytics of Georeferenced Big Data

Isam Mashhour Al Jawarneh, Luca Foschini, Paolo Bellavista

TL;DR

This paper introduces GeoRAP, a novel system for efficiently processing massive georeferenced data streams. By employing polygon simplification (using the Ramer-Douglas-Peucker algorithm) as a front-end filter before spatial stratified sampling, GeoRAP significantly reduces data volume and processing time for geospatial analytics, achieving an order of magnitude improvement in throughput while maintaining good accuracy.

What Problem Does This Paper Address?

The explosion of data from IoT devices, sensors, and GPS has led to an overwhelming volume of georeferenced data. Analyzing this "big geospatial data" is crucial for urban planning, mobility analysis, and environmental monitoring. However, traditional processing methods struggle with the sheer scale and complexity, leading to high latency and computational demands. Existing approximate query processing (AQP) techniques, particularly those using spatial stratified sampling, face a challenge: as the number of "strata" (geographic partitions) increases to improve accuracy, response times also increase, negating the benefits of sampling. This paper addresses the need for a system that can efficiently process these massive datasets in near real-time, providing accurate insights without being bogged down by data volume.

Methods

GeoRAP employs a two-pronged approach:

  1. Front-Stage Polygon Simplification: Before any sampling or processing, GeoRAP uses the Ramer-Douglas-Peucker (RDP) algorithm to simplify the boundary polygons of administrative regions (e.g., city districts). This reduces the number of vertices in these polygons, effectively simplifying the "study area coverage" and, crucially, reducing the number of geohashes (strata) needed to cover these simplified areas.
  2. Spatial Stratified-Like Sampling: After simplification, GeoRAP applies a spatial stratified-like sampling method. By minimizing the number of strata (thanks to the RDP simplification), this method can efficiently select representative samples from each stratum, leading to increased throughput and reduced response times while keeping accuracy loss in check.

The system is designed to work in both batch and online (streaming) modes, integrating with frameworks like Apache Spark.

Datasets

The authors evaluated GeoRAP using several real-world datasets:

  • San Francisco Uber Pickup Dataset: Anonymized GPS coordinates of Uber trips.
  • New York City Taxicab Trip Dataset: GPS locations and itinerary distances for taxi rides.
  • Shenzhen Electric Taxi GPS Mobility Dataset: Electric taxi trip data including speed.
  • NYC Low-Cost Air Quality Sensor Dataset: Data from sensors measuring air pollution levels (PM10, PM2.5, etc.).

These datasets represent mobility and environmental data, common in smart city applications.

Key Insights and Ideas

  • Polygon Simplification as a Pre-processing Step is Key: The core innovation is using geometric line simplification (RDP) before spatial sampling. This isn't just about reducing polygon complexity for visualization; it directly impacts the number of strata in the sampling process, which is a major bottleneck.
  • Reducing Strata is More Impactful Than Just Sampling: While stratified sampling is good, GeoRAP's approach of reducing the number of strata through simplification is what enables significant speedups. This is because managing fewer strata (geohashes) directly reduces computational overhead.
  • Trade-offs are Manageable: The paper demonstrates that aggressive simplification (low "number of PTR" - points to retain) can lead to a slight decrease in accuracy, but this trade-off is often acceptable for the substantial gains in speed and throughput, especially for applications like generating aggregate geo-maps where exact boundaries are less critical than overall density patterns.
  • Applicability Across Diverse Geospatial Data: The system's effectiveness is shown across mobility data and environmental sensor data, highlighting its versatility for various smart city analytics.

Key Results

  • Order of Magnitude Throughput Improvement: GeoRAP consistently outperforms baseline methods by an order of magnitude in terms of throughput.
  • Significant Reduction in Running Time: For example, a reduction in running time of roughly 13.5% was observed, with a corresponding reduction in tuples of only 2.2%.
  • Reduced File Sizes: The simplification process leads to smaller data footprints, with file sizes reduced to approximately 105 KB at a PTR of 1%.
  • Statistically Significant Accuracy: While there's a slight accuracy reduction, it's often within acceptable thresholds, and the paper shows GeoRAP achieving statistically good accuracy, sometimes even outperforming baselines in specific scenarios. For instance, in dynamic operation mode, GeoRAP showed a roughly 6.1% decrease in standard error compared to the baseline.
  • Effective for Geo-Stats and Aggregations: The system performs well for both single geo-statistical queries (like count and average speed) and aggregation queries (like Top-N region analysis).

Limitations and Future Work

  • RDP Algorithm Dependency: The current implementation relies on the Ramer-Douglas-Peucker algorithm. While effective, the paper notes that DP is a batch algorithm and future work could explore adaptive online versions.
  • Edge Cases in Simplification: The paper acknowledges that aggressive simplification can sometimes lead to spikes or minor distortions, though these are generally acceptable for the intended applications.
  • Future Work:
    • Spatial Join Integration: Incorporating a spatial join processor to further enhance performance when joining georeferenced data streams with disk-resident tables.
  • Space-Time Series Sampling: Extending GeoRAP to handle georeferenced time-series data.
  • Adaptive Online DP: Developing an online version of the DP algorithm that can adapt to incoming data streams without requiring data to be fully persisted.
  • Online Density-Based Clustering: Investigating methods to profile stream data and perform online density-based clustering before discarding polygon edges, to better understand data distribution.
  • Comparing Other Line Simplification Algorithms: Exploring the performance of other line simplification techniques within the GeoRAP framework.

Summary updated

Abstract

The unprecedented availability of sensor networks and GPS-enabled devices has caused the accumulation of voluminous georeferenced data streams. These data streams offer an opportunity to derive valuable insights and facilitate decision making for urban planning. However, processing and managing such data is challenging, given the size and multidimensionality of these data. Therefore, there is a growing interest in spatial approximate query processing depending on stratified-like sampling methods. However, in these solutions, as the number of strata increases, response time grows, thus counteracting the benefits of sampling. In this paper, we originally show the design and realization of a novel online geospatial approximate processing solution called GeoRAP. GeoRAP employs a front-stage filter based on the Ramer–Douglas–Peucker line simplification algorithm to reduce the size of study area coverage; thereafter, it employs a spatial stratified-like sampling method that minimizes the number of strata, thus increasing throughput and minimizing response time, while keeping the accuracy loss in check. Our method is applicable for various online and batch geospatial processing workloads, including complex geo-statistics, aggregation queries, and the generation of region-based aggregate geo-maps such as choropleth maps and heatmaps. We have extensively tested the performance of our prototyped solution with real-world big spatial data, and this paper shows that GeoRAP can outperform state-of-the-art baselines by an order of magnitude in terms of throughput while statistically obtaining results with good accuracy.
BibTeX
@inproceedings{jawarneh2023polygon,
  author = {Isam Mashhour Al Jawarneh and Luca Foschini and Paolo Bellavista},
  title = {{Polygon Simplification for the Efficient Approximate Analytics of Georeferenced Big Data}},
  booktitle = {Sensors},
  year = {2023},
  url = {https://openreview.net/forum?id=yLh8SRrfB9},
}
Figure