A GPU Approach to Subtrajectory Clustering Using the Fréchet Distance

Given a trajectory T we study the problem of reporting all subtrajectory clusters of T. To measure similarity between trajectory we choose the Frechet distance. We adapt an existing serial algorithm into a GPU parallel algorithm, resulting in substantial speed-ups, in some cases up to 11× faster, and increasing the size of the data that can be handled in reasonable amount of time, tests were performed on trajectories three times the size as previously managed. This is to the best of our knowledge not only the first GPU implementation of a subtrajectory clustering algorithm but also the first implementation using the continuous Frechet distance, instead of the discrete Frechet distance.