GCMF: an efficient end to end spatial join system over large polygonal datasets on GPGPU platform
Given two layers of large polygonal datasets, detecting those pairs of cross layer polygons which satisfy a join predicate, such as intersection or contain, is one of the most computationally intensive primitive operations in the spatial domain applications. In this work, we introduce GCMF, an end to end software system, that is able to handle spatial join (with ST_Intersect operation) over non indexed polygonal datasets with over 3 GB file size comprising more than 600, 000 polygons on a single GPU within less than 8 sec by applying innovative filter and refinement techniques. GCMF performs a two step filtering phase. 1) A sort based Minimum Bounding Rectangle (MBR) filtering step detects potentially overlapping polygon pairs up to 20 times faster than the optimized GEOS library routine. 2) A linear time Common MBR filtering step (based on the overlapping area of two given MBRs) that not only eliminates two third of the candidate polygon pairs but also reduces the number of edges to be considered in the refinement phase by 40 fold on an average based on our experimental results with real datasets. Furthermore, for the refinement phase, GCMF implements a load balanced parallel point in polygon and edge intersection tests over GPU. Our experimental results with three different real datasets show up to 39 fold end to end speedup versus optimized sequential routines of GEOS C+ library as well as PostgreSQL spatial database with PostGIS.
SIGSPATIAL/GIS