Speeding up Large-Scale Point-in-Polygon Test Based Spatial Join on GPUs
Department of Computer Science, The City College of the City University of New York, New York, NY, 10031
City College of New York, Technical Report, 2012
@article{zhang2012speeding,
title={Speeding up Large-Scale Point-in-Polygon Test Based Spatial Join on GPUs},
author={Zhang, J. and You, S.},
year={2012}
}
Point-in-Polygon (PIP) test is fundamental to spatial databases and GIS. Motivated by the slow response times in joining largescale point locations with polygons using traditional spatial databases and GIS and the massively data parallel computing power of commodity GPU devices, we have designed and developed an end-to-end system completely on GPUs to associate points with the polygons that they fall within. The system includes an efficient module to generate point quadrants that have at most K points from large-scale unordered points, a simple gridfile based spatial filtering approach to associate point quadrants and polygons, and, a PIP test module to assign polygons to points in a GPU computing block using both the block and thread level parallelisms. Experiments on joining 170 million points with more than 40 thousand polygons have resulted in a runtime of 11.165 seconds on an Nvidia Quadro 6000 GPU device. Compared with a baseline serial CPU implementation using stateof-the-art open source GIS packages which requires 15.223 hours to complete, a speedup of 4,910X has been achieved. We further discuss several factors and parameters that may affect the system performance.
July 27, 2012 by hgpu
