A New Design of High-Performance Large-Scale GIS Computing at a Finer Spatial Granularity: A Case Study of Spatial Join with Spark for Sustainability

Feng Zhang, Jingwei Zhou, Renyi Liu, Zhenhong Du, Xinyue YeSustainability 2016 · DOI

TL;DR

This paper introduces Spatial Join with Spark (SJS), a novel, high-performance algorithm designed for large-scale spatial join operations on massive geospatial datasets. SJS leverages Spark's in-memory computing capabilities and a unique repartitioning strategy to significantly outperform existing MapReduce and Spark-based spatial join methods, enabling faster and more efficient analysis for sustainability research.

What Problem Does This Paper Address?

Sustainability research increasingly relies on analyzing vast amounts of geospatial data at increasingly fine granularities. This rapid growth in data volume presents a significant challenge for traditional spatial analysis tools, particularly for spatial join operations, which are crucial for understanding spatial relationships and integrating diverse data sources. Existing methods, often built on MapReduce, struggle with performance bottlenecks due to disk I/O and inefficient data partitioning, especially when dealing with massive datasets. The paper aims to bridge this gap by developing a more efficient and scalable spatial join solution using modern big data processing frameworks.

Methods

The core of the proposed solution is the Spatial Join with Spark (SJS) algorithm, which is designed to run on Apache Spark. SJS breaks down the spatial join process into four key phases:

  • Partition Phase: Instead of complex sampling or indexing, SJS employs a simple, uniform spatial grid to partition spatial objects. This approach aims to reduce preprocessing time and avoid the data skew issues that plague other methods.
  • Partition Join Phase: This phase leverages Spark's built-in join transformation to efficiently combine partitions that share common IDs. This is a coarse-grained, initial filtering step.
  • Repartition Phase: This is a novel contribution. SJS introduces a "calculation-evaluating model" to estimate the computational cost of local joins within each partition. If a partition's estimated cost exceeds a threshold, it's dynamically repartitioned in-memory to balance the workload and prevent CPU overload, thus mitigating data skew. This is done without disk access.
  • In-Memory Join Phase: The final stage utilizes an optimized in-memory spatial join algorithm. The paper compares several options and settles on the R*-tree index nested-loop join for its high space utilization and retrieval speed, performing the join in parallel across the refined partitions.

Datasets

The experiments were conducted using real-world geospatial datasets from the TIGER (Topologically-Integrated Geographic Encoding and Referencing) and OpenStreetMap projects. These datasets include:

  • all ways (AWY): Polylines
  • edges (ED): Polygons
  • linearwater (LW): Polylines
  • areawater (AW): Polygons
  • arealm (LM): Polygons
  • primaryroads (PR): Polylines

These datasets vary significantly in size, ranging from 77 MB to 59.55 GB, allowing for comprehensive evaluation of SJS's scalability.

Key Insights and Ideas

  • Uniform Grid Partitioning is Sufficient: The paper demonstrates that a simple uniform grid partitioning strategy, when combined with intelligent repartitioning, can be more effective and faster than complex indexing-based methods for initial data distribution.
  • Dynamic In-Memory Repartitioning is Crucial: The "calculation-evaluating model" for dynamic repartitioning is a key innovation. By predicting computational load rather than just data size, SJS can proactively address data skew and ensure balanced processing across partitions, a significant improvement over static partitioning.
  • Spark's In-Memory Power: The research effectively harnesses Spark's distributed in-memory computing capabilities to minimize disk I/O, a major bottleneck in traditional MapReduce-based spatial join.
  • R*-tree for Local Joins: The choice of R*-tree for the in-memory local join phase proves to be a strong performer, offering a good balance of space utilization and query speed.

Key Results

  • Outperforms Existing Methods: SJS consistently outperformed earlier MapReduce-based spatial join algorithms (SHADOOP-SJMR, SHADOOP-DJ) and a comparable Spark-based algorithm (SpatialSpark) across various dataset sizes.
  • Significant Speedup: In performance comparisons, SJS showed significantly better execution times, especially with larger datasets. For instance, in Figure 8, SJS achieved execution times orders of magnitude lower than its competitors for the largest input sizes.
  • Repartitioning Benefits: SJS with its repartitioning strategy reduced total execution time by 5%-25% compared to not using repartitioning, even without considering the initial partitioning cost.
  • Scalability: The performance of SJS scales well with an increasing number of nodes, demonstrating its suitability for large-scale cloud environments.

Limitations and Future Work

  • R*-tree Limitations: While R*-tree is effective for 2D spatial data, the authors acknowledge that it may not be suitable for high-dimensional geographic objects, suggesting future work in exploring high-dimensional spatial indexes.
  • Temporal Dimension: The current work focuses on static spatial joins. Future research aims to incorporate the temporal dimension to enable spatiotemporal join analysis.
  • Algorithm Enhancements: The authors plan to explore integrating other advanced in-memory spatial join methods (like TOUCH) into Spark and further optimize local join performance.
  • Computational Cost Evaluation: While the calculation-evaluating model is a key contribution, its accuracy and efficiency for a wider range of spatial predicates and object complexities could be further investigated.

Summary updated

Abstract

Sustainability research faces many challenges as respective environmental, urban and regional contexts are experiencing rapid changes at an unprecedented spatial granularity level, which involves growing massive data and the need for spatial relationship detection at a faster pace. Spatial join is a fundamental method for making data more informative with respect to spatial relations. The dramatic growth of data volumes has led to increased focus on high-performance large-scale spatial join. In this paper, we present Spatial Join with Spark (SJS), a proposed high-performance algorithm, that uses a simple, but efficient, uniform spatial grid to partition datasets and joins the partitions with the built-in join transformation of Spark. SJS utilizes the distributed in-memory iterative computation of Spark, then introduces a calculation-evaluating model and in-memory spatial repartition technology, which optimize the initial partition by evaluating the calculation amount of local join algorithms without any disk access. We compare four in-memory spatial join algorithms in SJS for further performance improvement. Based on extensive experiments with real-world data, we conclude that SJS outperforms the Spark and MapReduce implementations of earlier spatial join approaches. This study demonstrates that it is promising to leverage high-performance computing for large-scale spatial join analysis. The availability of large-sized geo-referenced datasets along with the high-performance computing technology can raise great opportunities for sustainability research on whether and how these new trends in data and technology can be utilized to help detect the associated trends and patterns in the human-environment dynamics.
BibTeX
@inproceedings{zhang2016new,
  author = {Feng Zhang and Jingwei Zhou and Renyi Liu and Zhenhong Du and Xinyue Ye},
  title = {{A New Design of High-Performance Large-Scale GIS Computing at a Finer Spatial Granularity: A Case Study of Spatial Join with Spark for Sustainability}},
  booktitle = {Sustainability},
  year = {2016},
  doi = {10.3390/su8090926},
}
Figure