Processing similarity-based trajectory query on GPUs


Volumes of GPS recorded trajectory data in ubiquitous urban sensing applications are increasing fast. Many trajectory queries are both I/O and computing intensive. In this study, we propose to develop the U2STRA prototype system to efficiently manage large-scale GPS trajectory data using General Purpose computing on Graphics Processing Units (GPGPU) technologies. Towards this end, we have developed a trajectory data layout schema using simple in-memory array structures which is not only flexible for data accesses but also cache friendly. We have further developed an end-to-end trajectory similarity query processing technique on GPUs. Our experiments on two publically available large trajectory datasets (GeoLife and T-Drive) have demonstrated the efficiency of massively data parallel GPGPU computing. An impressive 87X speedup for spatial aggregations of GPS point locations and 25-40X speedups for trajectory queries over serial CPU implementations have been achieved. The U2STRA system has also been integrated with commercial desktop and Web-based GIS systems and spatial databases for visual exploration purposes.


Related Publications:
Jianting Zhang, Simin You and Le Gruenwald (2012). U2STRA: High-Performance Data Management of Ubiquitous Urban Sensing Trajectories on GPGPUs. Proceedings of the ACM CDMW Workshop. [PDF]