BEGIN:VCALENDAR
PRODID:-//Microsoft Corporation//Outlook MIMEDIR//EN
VERSION:1.0
BEGIN:VEVENT
DTSTART:20141120T171500Z
DTEND:20141120T173000Z
LOCATION:386-87
DESCRIPTION;ENCODING=QUOTED-PRINTABLE: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.
SUMMARY:High Performance Computing over Geo-Spatial data: A Summary of Results
PRIORITY:3
END:VEVENT
END:VCALENDAR