Out-of-Core Parallel Spatial Join Outperforming In-Memory Systems: A BFS-DFS Hybrid Approach

Spatial join is a fundamental operation in many applications such as geographic information system (GIS) and simulation sciences. Recent works advocate in-memory spatial join for efficiency, but they require entire datasets to be loaded into memory, and they were only tested on small to medium-sized datasets. In this paper, we target out-of-core parallel spatial join to handle massive data, and surprisingly, we find that our solution can be orders of magnitude faster than the state-of-the-art in-memory solutions. Our system, called T-Spatial, decomposes a spatial-join job into tasks to expose massive parallelism opportunities. A BFS-DFS hybrid execution model is designed to enable memory-bounded high-throughput task processing, which exploits spatial locality to reuse cached data as much as possible to reduce disk IOs. T-Spatial also effectively overlaps computations with disk IOs by prefetching, and integrates a few optimization techniques including work stealing to avoid stragglers, write contention mitigation under multithreading, and a NUMA-aware design. Extensive experiments show that T-Spatial significantly outperforms state-of-the-art in-memory approaches (e.g., PBSM, TOUCH) and cloud-based parallel spatial systems (e.g., Apache Sedona) with 2–3 orders of magnitude of speedup ratio, and it is the first in the literature to test spatial joins on billion-scale datasets.