Through the use of location-sensing devices, it has been possible to collect very large datasets of trajectories. These datasets make it possible to issue spatio-temporal queries with which users can gather information about the characteristics of the movements of objects, derive patterns from that information, and understand the objects themselves. Among such spatio-temporal queries that can be issued is the top-K trajectory similarity query. This query finds many applications, such as bird migration analysis in ecology and trajectory sharing in social networks. However, the large size of the trajectory query sets and databases poses significant computational challenges. In this work, we propose a parallel GPGPU algorithm Top-KaBT that is specifically designed to reduce the size of the candidate set generated while processing these queries, and in doing so strives to address these computational challenges. The experiments show that the state of the art top-K trajectory similarity query processing algorithm on GPGPUs, TKSimGPU, achieves a 6.44X speedup in query processing time when combined with our algorithm and a 13X speedup over a GPGPU algorithm that uses exhaustive search.
|Original language||English (US)|
|Title of host publication||Proceedings - 2016 IEEE International Congress on Big Data, BigData Congress 2016|
|Editors||Calton Pu, Geoffrey Fox, Ernesto Damiani|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||8|
|State||Published - Oct 5 2016|
|Event||5th IEEE International Congress on Big Data, BigData Congress 2016 - San Francisco, United States|
Duration: Jun 27 2016 → Jul 2 2016
|Name||Proceedings - 2016 IEEE International Congress on Big Data, BigData Congress 2016|
|Other||5th IEEE International Congress on Big Data, BigData Congress 2016|
|Period||6/27/16 → 7/2/16|
Bibliographical noteFunding Information:
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.
© 2016 IEEE.
Copyright 2017 Elsevier B.V., All rights reserved.
- High performance
- Trajectory similarity