There exist large datasets containing the sequences of points that moving objects occupy in space as time goes by. Such sequences of moving objects are known as trajectories. Being able to issue queries that allow the extraction of patterns from the movements of these objects is important to many real world applications, such as urban planning in transportation and bird migration tracking in ecology. One example of such queries is the top-K trajectory similarity query. This type of query receives as input arguments two sets P and Q of trajectories and a positive integer k, and seeks to find for every trajectory p in P the set of k trajectories in Q that are the most similar to p. However, querying these trajectory data is both compute and I/O intensive. In this paper we explore the potential of GPGPUs for supporting, in a scalable manner, top-K trajectory similarity queries. To this end, we propose an algorithm, called TKSimGPU, that incorporates parallelization strategies in order to answer this type of trajectory queries. We conducted experiments comparing the throughput of top-K trajectory similarity queries performed on multicore CPUs and GPGPUs using a large scale real world trajectory dataset. The experiments show that TKSimGPU achieved a 3.37x speedup in query processing time over exhaustive search on a GPU, and a 4.9x speedup in query processing time on a 12-core CPU architecture.
|Original language||English (US)|
|Title of host publication||Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015|
|Editors||Feng Luo, Kemafor Ogan, Mohammed J. Zaki, Laura Haas, Beng Chin Ooi, Vipin Kumar, Sudarsan Rachuri, Saumyadipta Pyne, Howard Ho, Xiaohua Hu, Shipeng Yu, Morris Hui-I Hsiao, Jian Li|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||9|
|State||Published - Dec 22 2015|
|Event||3rd IEEE International Conference on Big Data, IEEE Big Data 2015 - Santa Clara, United States|
Duration: Oct 29 2015 → Nov 1 2015
|Name||Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015|
|Other||3rd IEEE International Conference on Big Data, IEEE Big Data 2015|
|Period||10/29/15 → 11/1/15|
Bibliographical noteFunding Information:
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.
© 2015 IEEE.
- High performance
- Trajectory similarity