Grid-Based Method for GPS Route Analysis for Retrieval
Radu Mariescu-Istodor, Pasi Fränti
ACM Transactions on Spatial Algorithms and Systems 3 (3), 8, pp. 1-28, 2017

Grids are commonly used for presenting spatial data. However, they have not been previously used for analyzing GPS trajectories. Instead, slower and more complicated algorithms based on individual point-pair comparison have been used. We demonstrate how a grid representation can be used to compute four different route measures: novelty, noteworthiness, similarity and inclusion. The measures may be used in several applications such as:

We compare our proposed route similarity measure, C-SIM, to 8 popular alternatives including edit distance, longest common subsequence and Frechet distance. The proposed measure is simple to implement and we give a fast, linear time algorithm for the task. It works well under noise, changes in sampling rate and point shifting. We demonstrate that using the grid, a route similarity ranking can be computed in real-time on the Mopsi2014 route database which consists of over 6,000 routes. This ranking is an extension of the most similar route search and contains an ordered list of all similar routes from the database. The real-time search is due to indexing the cell database and comes at the cost of spending 80% more memory space for the index. The methods are implemented in Mopsi.

We present an interactive environment for comparing different route similarity measures. This environment uses the following open API for computing route similarity measures:
C-SIM(proposed)
LCSSLongest Common Subsequence
EDREdit Distance on Real sequence
DTWDynamic Time Warping
FastDTW
ERPEdit distance with Real Penalty
Euclidean
Hausdorff
Frechet

Disclaimer: The data might contain copyrighted material and should not be used for any purpose other than data analysis for scientific research.