  Processing moving object trajectories arises in many application domains and
has been addressed by practitioners in the spatiotemporal database and
Geographical Information System communities. In this work, we focus on a
trajectory similarity search, the distance threshold query, which finds all
trajectories within a given distance d of a search trajectory over a time
interval. We demonstrate the performance of a multithreaded implementation
which features the use of an R-tree index and which has high parallel
efficiency (78%-90%). We introduce a GPGPU implementation which avoids the use
of index-trees, and instead features a GPU-friendly indexing method. We compare
the performance of the multithreaded and GPU implementations, and show that a
speedup can be obtained using the latter. We propose two classes of algorithms,
SetSplit and GreedySetSplit, to create efficient query batches that reduce
memory pressure and computational cost on the GPU. However, we find that using
fixed-size batches is sufficiently efficient in practice. We develop an
empirical performance model for our GPGPU implementation that can be used to
predict the response time of the distance threshold query. This model can be
used to pick a good query batch size.

Databases;Distributed, Parallel, and Cluster Computing