104. MPI-GIS : High Performance Computing and I/O for Spatial Overlay and Join
Authors: Satish Puri (Marquette University)
Abstract: For certain GIS and Spatial Database applications, spatial overlay and join on two or more layers of geo-spatial data may be necessary. However, using a sequential paradigm to process them is time-consuming. For large datasets, I/O, spatial indexing, and geometric refinement phase are time consuming. These operations involve irregular I/O due to varying number of vertices in different shapes and irregular computations without well-defined communication pattern due to irregular spatial and/or temporal task or data distributions. These irregularities makes parallelization, partitioning, and load balancing more challenging.
We have undertaken parallelization of polygon clipping and overlay algorithms, and spatial join using GPU and MPI. We briefly describe our MPI-GIS system and highlight our work on parallel I/O for OpenStreetMap data. We also present a parallel algorithm for Intersection of polygons which is an elementary operations in polygon overlay. Its time complexity is O((n+k)logn) where k is the number of intersections.
Two-page extended abstract: pdf