Distance Threshold Similarity Searches on Spatiotemporal Trajectories using GPGPU

Michael Gowanlock, Henri Casanova
Dept. of Information and Computer Sciences and NASA Astrobiology Institute University of Hawai’i, Honolulu, HI, U.S.A.
21st annual IEEE International Conference on High Performance Computing (HiPC 2014), 2014


   title={Distance Threshold Similarity Searches on Spatiotemporal Trajectories using GPGPU},

   author={Gowanlock, Michael and Casanova, Henri},



Download Download (PDF)   View View   Source Source   



The processing of moving object trajectories arises in many application domains. We focus on a trajectory similarity search, the distance threshold search, which finds all trajectories within a given distance of a query trajectory over a time interval. A multithreaded CPU implementation that makes use of an in-memory R-tree index can achieve high parallel efficiency. We propose a GPGPU implementation that avoids index-trees altogether and instead features a GPU-friendly indexing scheme. We show that our GPU implementation compares well to the CPU implementation. One interesting question is that of creating efficient query batches (so as to reduce both memory pressure and computation cost on the GPU). We design algorithms for creating such batches, and we find that using fixed-size batches is sufficient in practice. We develop an empirical response time model that can be used to pick a good batch size.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: