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. |
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