High-Performance Spatial Join Processing on GPGPUs with Applications to Large-Scale Taxi Trip Data

Jianting Zhang, Simin You, Le Gruenwald
Dept. of Computer Science, City College of New York, New York City, NY, 10031
City College of New York, Technical Report, 2012


   title={High-Performance Spatial Join Processing on GPGPUs with Applications to Large-Scale Taxi Trip Data},

   author={Zhang, J. and You, S. and Gruenwald, L.},


   institution={Technical report online at http://geoteci. engr. ccny. cuny. edu/pub/nnsp_tr. pdf}


Download Download (PDF)   View View   Source Source   



Spatially joining GPS recorded locations with infrastructure data, such as points of interests, road network, land cover and different types of zones, and assigning a point with its nearest polyline or polygon is a prerequisite for trip related analysis, which is becoming increasingly important in ubiquitous computing. However, existing spatial databases and GIS are incapable of handling large-scale data. The poor performance of these systems that takes tens of hours to dozens of days to complete such a commonly used spatial join query is undesirable. By leveraging several high-performance techniques, including massive data parallel General Purpose computing on Graphics Processing Units (GPGPU) technologies and cache friendly main-memory data structures, we are able to design an efficient spatial join query processing system. The experiments using a commodity workstation equipped with a Nvidia GPU device and real NYC taxi trip location data show that our system can join 170 million points with nearly a million polygons based on the nearest neighbor principle in about 33 seconds The performance represents a 3-4 orders of speedup when compared with an optimized serial CPU implementation using two leading open source packages for spatial indexing and spatial data management, respectively. We report our designs and implementations of GPU based filtering and refinement in spatial join processing and discuss the implications of modern hardware architectures for spatial databases and GIS.
Rating: 1.7/5. From 3 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: