DescriptionGiven two layers of large polygonal datasets, detecting those pairs of cross-layer polygons which satisfy a join predicate, such as intersection, is one of the most computationally intensive primitive operations in the spatial domain applications. There are alternative solutions for this ill-structured problem in literature. However, none of them is designed to take advantage of heterogeneous clusters equipped with GPU accelerators to process big spatial data efficiently.
In this research, we propose a distributed heterogeneous HPC platform for spatial join processing based on two-step filter and refinement approach. This work includes two main parts. First, we introduce a set of novel GPU-suited data structures and algorithms. Proof of correctness and analysis is also provided for each algorithm. Second, by applying these new techniques, we propose several GPU-based spatial join systems for various operations such as ST_intersect and polygon overlay to improve the performance of current state of the art systems.