A Spatial Join Algorithm Based on a Non-uniform Grid Technique over GPGPU
Danial Aghajarian, Sushil K. Prasad · 2017
Grid-based techniques are well-suited for spatial join algorithms over General Purpose Graphic Processing Unit (GPGPU) architectures because of their non-hierarchical structure. However, these techniques are well-established years before the existence of GPU computing. As a result, they do not fully take advantage of many-core architectures. Last year, we had introduced a spatial join GPU system based on discarding even those cross-layer pairs of polygons whose Minimum Bounding Rectangles (MBRs) intersect but their rectangular intersection does not contain edges from both layers. These MBR intersections are called Common MBRs. In this extended abstract, we briefly introduce CMF-Grid: a non-uniform GPU-based grid technique over such Common MBRs, that can be used in polygonal spatial join operations such as overlay, edge-intersection etc. to significantly reduce their computationally-extensive refinement phase workload. Based on our experimental results on real datasets, CMF-Grid can cut down the refinement phase workload by more than 30, 000 times that of all-to-all algorithms and it improves upon its predecessor, CMF filter, by 700 times. Our upgraded spatial join system with ST_intersect predicate is able to process more than 600, 000 polygons with more than 2 billions edges on a single GPU in less than a second end-to-end processing time that is 225% time improvement compared to GCMF, the state of the art GPU-based system. The system also achieves up to 200-fold end-to-end speedup versus the best optimized sequential routines of GEOS C++ library as well as PostgreSQL spatial database with PostGIS.