Point-to-Polygon Spatial Join on GPUs based on Windowed Nearest-Neighbor Search

Given a point dataset and a polygonal dataset, the point-in-polygon test based spatial join assigns a polygon identifier to each poin where the polygon uniquely contains the point. Our experiments have shown that our system is able to join 170 million taxi pickup locations with 735,488 NYC tax block polygons in 33 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 30.5 hours to complete, a speedup of 3,325X has been achieved.


 Related Publications:

1) Jianting Zhang, Simin You and Le Gruenwald (2012). Speeding High-Performance Spatial Join Processing on GPGPUs with Applications to Large-Scale Taxi Trip Data. Technical Report. [Link]
2) Jianting Zhang, Simin You* and Le Gruenwald (2014). High-Performance Spatial Query Processing on Big Taxi Trip Data using GPGPUs. To appear in Proceedings of IEEE International Congress on BigData. (8 formatted pages - IEEE Conf.) [Link]

CPU serial implementation source code:
1) Code to generate R-Tree for inexing polygons using libspatialindex [link]
2) Code to query polygon R-Tree and compute shorest distance using
libspatialindex and GDAL [link]