high performance computing on graphics processing units: hgpu.org

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.