Spatial Join on GPUs based on Point-in-Polygon Test

Given a point dataset and a polygonal dataset, the point-in-polygon test based spatial join assigns a polygon identifier to each point where the polygon uniquely contains the point. Our experiments have shown that our system is able to join 168 million taxi pickup locations with 43,252 NYC 2010 census blocks in 11 seconds on an Nvidia Quadro 6000 GPU device. Compared with a baseline serial CPU implementation using state-of-the-art open source GIS packages which requires 15.223 hours to complete, a speedup of 4,910X has been achieved.

Related Publications:

1) Jianting Zhang and Simin You (2012). Speeding up Large-Scale Point-in-Polygon Test Based Spatial Join on GPUs. To appear in ACM BigSpatial'12 Workshop. [Link]