TKSimGPU: A parallel top-K trajectory similarity query processing algorithm for GPGPUs

Eleazar Leal, Le Gruenwald, Jianting Zhang, Simin You

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015
EditorsFeng 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
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages461-469
Number of pages9
ISBN (Electronic)9781479999255
DOIs
StatePublished - Dec 22 2015
Event3rd IEEE International Conference on Big Data, IEEE Big Data 2015 - Santa Clara, United States
Duration: Oct 29 2015Nov 1 2015

Publication series

NameProceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015

Other

Other3rd IEEE International Conference on Big Data, IEEE Big Data 2015
CountryUnited States
CitySanta Clara
Period10/29/1511/1/15

    Fingerprint

Keywords

  • GPGPU
  • High performance
  • Trajectory
  • Trajectory similarity

Cite this

Leal, E., Gruenwald, L., Zhang, J., & You, S. (2015). TKSimGPU: A parallel top-K trajectory similarity query processing algorithm for GPGPUs. In F. Luo, K. Ogan, M. J. Zaki, L. Haas, B. C. Ooi, V. Kumar, S. Rachuri, S. Pyne, H. Ho, X. Hu, S. Yu, M. H-I. Hsiao, & J. Li (Eds.), Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015 (pp. 461-469). [7363787] (Proceedings - 2015 IEEE International Conference on Big Data, IEEE Big Data 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BigData.2015.7363787