The International Conference for High Performance Computing, Networking, Storage and Analysis |

Student: Satish Puri (Georgia State University)

Advisor: Sushil Prasad (Georgia State University)

Abstract: Polygon overlay and polygon clipping are one of the complex operations in Geographic Information Systems (GIS), Computer Graphics, and VLSI CAD. We present the ﬁrst output-sensitive parallel algorithm, which can perform geometric intersection, union, and difference operations in O(logn) time using O(n + k) processors, where n is the number of polygonal vertices and k is the number of edge intersections. This is cost-optimal when compared to sequential plane-sweep based algorithm and superior to O(n^2logn) time parallel algorithm by Karinthi, Srinivas, and Almasi. We have also developed two systems 1) MPI-GIS and 2) Hadoop Topology Suite for distributed polygon overlay using a cluster of nodes. Out MPI and GPU based system achieves 44X speedup while processing about 600K polygons in two real-world GIS shapefiles 1)USA Detailed Water Bodies and 2)USA Block Group Boundaries) within 20 seconds on a 32-node (8 cores each) IBM iDataPlex cluster interconnected by InfiniBand technology.

Poster: pdf

Summary: pdf

Doctoral Showcase Index