With the increasing prevalence of location sensor devices like GPS, it has been possible to collect large datasets of a special type of spatio-temporal data called trajectory data. A trajectory is a discrete sequence of positions that a moving object occupies in space as time passes. Such large datasets enable researchers to study the behavior of the objects describing these movements by issuing spatial queries. Among the queries that can be issued are top-K trajectory similarity queries, which retrieve the K most similar trajectories to a given query trajectory. This query has applications in many areas, such as urban planning, ecology and social networking; however, this query is computationally expensive. In this work, we introduce a new parallel top-K trajectory similarity query technique for GPUs, FastTopK, to deal with these challenges. Our experiments on two large real-life datasets showed that FastTopK produces on average 107.96X smaller candidate result sets, and 3.36X faster query execution times than the existing state-of-the-art technique, TKSimGPU.
|Original language||English (US)|
|Title of host publication||Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018|
|Editors||Yang Song, Bing Liu, Kisung Lee, Naoki Abe, Calton Pu, Mu Qiao, Nesreen Ahmed, Donald Kossmann, Jeffrey Saltz, Jiliang Tang, Jingrui He, Huan Liu, Xiaohua Hu|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||6|
|State||Published - Jan 22 2019|
|Event||2018 IEEE International Conference on Big Data, Big Data 2018 - Seattle, United States|
Duration: Dec 10 2018 → Dec 13 2018
|Name||Proceedings - 2018 IEEE International Conference on Big Data, Big Data 2018|
|Conference||2018 IEEE International Conference on Big Data, Big Data 2018|
|Period||12/10/18 → 12/13/18|
Bibliographical noteFunding Information:
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.
ACKNOWLEDGMENT This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.
© 2018 IEEE.
- GPU computing
- query processing
- trajectory similarity