An Effective High-Performance Multiway Spatial Join Algorithm with Spark

Zhenhong Du, Xianwei Zhao, Xinyue Ye, Jingwei Zhou, Feng Zhang, Renyi LiuIsprs Int. J. geo inf 2017 · DOI

TL;DR

This paper introduces MSJS, a novel high-performance algorithm for multiway spatial joins on massive datasets using Apache Spark. By leveraging Spark's in-memory processing and a cascaded pairwise join strategy, MSJS significantly outperforms existing MapReduce-based approaches, addressing a critical bottleneck in large-scale geospatial analysis.

What Problem Does This Paper Address?

Geographic Information Systems (GIS) rely heavily on spatial analysis, with spatial joins being a fundamental operation for integrating and understanding spatial data. A "multiway spatial join" extends this by involving more than two datasets, for example, finding all forests crossed by rivers in specific states. As the volume of spatial data explodes, traditional methods struggle to keep up, leading to computational bottlenecks. While parallel computing platforms like MapReduce and Spark offer solutions, efficiently handling multiway spatial joins in a distributed, in-memory environment remains a challenge. Previous approaches often involve extensive data replication or high disk I/O, leading to performance issues. This paper aims to bridge this gap by developing a Spark-native, high-performance multiway spatial join algorithm.

Methods

The core of MSJS lies in its adaptation of a cascaded pairwise join strategy to Spark's distributed in-memory computing capabilities. The algorithm proceeds in three main phases:

  1. Partition Phase: Datasets are partitioned using a uniform grid. Unlike traditional methods that might replicate objects across multiple partitions to ensure completeness, MSJS focuses on partitioning based on an object's Minimum Bounding Rectangle (MBR) overlap with grid tiles. This is crucial for in-memory processing to avoid excessive memory usage.
  2. Group Partition Phase: Objects with the same partition ID are grouped together. This is achieved using Spark's groupByKey transformation, effectively creating lists of objects for each partition ID.
  3. Cascaded Pairwise Join Phase: This is the most innovative part. The multiway join is decomposed into a series of pairwise joins. For each pairwise join (except the last), the algorithm performs the following:
  4. Join Partitions: Datasets with matching partition IDs are joined using Spark's join transformation.
  5. R*-tree Nested-Loop Join: An R*-tree spatial index is used to efficiently perform the filter and refinement steps of the spatial join within each partition. This is a standard technique for optimizing spatial joins.
  6. Reduce and Cache: Intermediate results are reduced by merging object IDs. Crucially, Spark's in-memory caching is leveraged to store intermediate results, avoiding costly disk I/O that plagues MapReduce-based methods. This iterative in-memory computation is a key advantage of Spark.
  7. Repartition: The results are repartitioned to prepare for the next pairwise join in the cascade.

This cascaded approach, combined with Spark's in-memory processing, significantly reduces disk I/O and communication costs compared to traditional MapReduce solutions.

Datasets

The experiments utilized real-world TIGER datasets, which are commonly used in GIS research. These datasets include:

  • edges (ED): 72,729,686 Polygons, 62 GB
  • linearwater (LW): 5,857,442 Polylines, 18.3 GB
  • areawater (AW): 2,298,808 Polygons, 6.5 GB
  • arealandmark (LM): 121,960 Polygons, 406 MB
  • primaryroads (PR): 13,373 Polylines, 77 MB

These datasets vary significantly in size and geometry type, allowing for comprehensive evaluation of MSJS's performance under different conditions. The paper does not introduce new benchmark datasets but uses established ones.

Key Insights and Ideas

  • Spark's In-Memory Advantage: The paper strongly highlights how Spark's ability to cache intermediate results in memory is the key enabler for high-performance cascaded spatial joins. This directly addresses the disk I/O bottleneck of MapReduce.
  • Cascaded Pairwise Joins for Multiway: Decomposing a complex multiway join into a series of simpler pairwise joins, and then optimizing each step with in-memory processing, is an effective strategy.
  • R*-tree for Efficient Refinement: The continued use of R*-tree indexing for the refinement stage within each partition demonstrates that established spatial indexing techniques remain valuable even in a distributed, in-memory context.
  • Scalability with Nodes: MSJS exhibits strong scalability, with performance significantly improving as the number of compute nodes increases. This is crucial for handling massive datasets.
  • Optimal Threading: Performance peaks at 4 threads per node, aligning with the number of CPU cores, suggesting that beyond this point, contention or memory limitations might arise.
  • Input Sequence Matters: The order in which datasets are joined can significantly impact performance, especially when dataset sizes vary. Joining smaller datasets first appears to be a more efficient strategy.

Key Results

  • Superior Performance: MSJS consistently outperformed existing MapReduce-based multiway spatial join algorithms (HADOOP-CAS, HADOOP-CP, HADOOP-ϵCP) by a significant margin across various dataset sizes.
  • Scalability: Performance increases substantially with the number of nodes, indicating good scalability.
  • Optimal Threading: Peak performance was achieved with 4 threads per node.
  • Partitioning Impact: An optimal partition number (e.g., 200x400 grids) was identified for balancing data per partition and avoiding excessive duplicates, though this can vary with input size.
  • Linear Relationship: The paper suggests a linear relationship between MSJS execution time and input data volume.

Limitations and Future Work

  • Limitations:
    • The paper notes that while MSJS is efficient, there might be "extra refinement processes" in the cascaded join phase that could be further optimized.
  • The optimal number of partitions can be dataset-dependent and requires careful tuning.
  • Performance can degrade if memory is insufficient, potentially leading to termination.
  • Future Work:
    • The authors plan to develop novel methods to reduce the extra refinement processes in the cascaded pairwise join phase to further improve performance.
  • Further research into optimizing the input sequence selection for MSJS is suggested.

Summary updated

BibTeX
@article{du2017effective,
  author = {Zhenhong Du and Xianwei Zhao and Xinyue Ye and Jingwei Zhou and Feng Zhang and Renyi Liu},
  title = {{An Effective High-Performance Multiway Spatial Join Algorithm with Spark}},
  journal = {Isprs Int. J. geo inf},
  year = {2017},
  doi = {10.3390/ijgi6040096},
}
Figure