Distance Threshold Similarity Searches: Efficient Trajectory Indexing on the GPU

Michael Gowanlock, Henri Casanova

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Applications in many domains perform searches over datasets that contain moving object trajectories. A common class of searches are similarity searches that attempt to identify trajectories with similar characteristics. In this work, we focus on the distance threshold similarity search that finds all trajectories within a given distance of a query trajectory over a time interval. This search involves large numbers of Euclidean moving distance calculations, thus making it a good candidate for execution on manycore platforms such as GPUs. However, low search response time is preconditioned on efficient indexing of trajectory data. We propose three indexing schemes designed for the GPU, with spatial, temporal and spatiotemporal selectivity. These schemes differ significantly from traditional tree-based indexing schemes that have been previously proposed for CPU executions. We evaluate implementations of our proposed indexing schemes using two synthetic and one real-world astrophysics dataset, showing under which conditions each scheme achieves high performance. Our broad finding is that a GPU implementation, provided an appropriate indexing scheme is used, can outperform a multithreaded CPU implementation that uses a state-of-the-art index tree. In particular, the performance improvement is large for regimes that are relevant for classes of real-world applications, thereby demonstrating that the GPU is an attractive platform for searching and processing moving object trajectories.

Original languageEnglish (US)
Article number7330012
Pages (from-to)2533-2545
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume27
Issue number9
DOIs
StatePublished - Sep 1 2016
Externally publishedYes

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Distance Threshold Similarity Searches: Efficient Trajectory Indexing on the GPU'. Together they form a unique fingerprint.

Cite this