Towards an efficient Top-K trajectory similarity query processing algorithm for big trajectory data on GPGPUs

Eleazar Leal, Le Gruenwald, Jianting Zhang, Simin You

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

1 Scopus citations

Abstract

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 languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE International Congress on Big Data, BigData Congress 2016
EditorsCalton Pu, Geoffrey Fox, Ernesto Damiani
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages206-213
Number of pages8
ISBN (Electronic)9781509026227
DOIs
StatePublished - Oct 5 2016
Event5th IEEE International Congress on Big Data, BigData Congress 2016 - San Francisco, United States
Duration: Jun 27 2016Jul 2 2016

Publication series

NameProceedings - 2016 IEEE International Congress on Big Data, BigData Congress 2016

Other

Other5th IEEE International Congress on Big Data, BigData Congress 2016
CountryUnited States
CitySan Francisco
Period6/27/167/2/16

Bibliographical note

Funding Information:
This work is supported in part by the National Science Foundation under Grant No. 1302439 and 1302423.

Publisher Copyright:
© 2016 IEEE.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

  • GPGPU
  • High performance
  • Trajectory
  • Trajectory similarity

Fingerprint Dive into the research topics of 'Towards an efficient Top-K trajectory similarity query processing algorithm for big trajectory data on GPGPUs'. Together they form a unique fingerprint.

Cite this