Efficient Algorithm for time-based similarity of trajectory on graph

The analysis of similar trajectories in a network provides useful information for route recommendation or fraud detection. In this thesis, we are interested in algorithms to efficiently retrieve similar trajectories. Many studies have focused on retrieving similar trajectories by extracting the geometrical information of trajectories. We provide a similarity function by making use of both the temporal aspect of trajectories and the structure of the underlying network. We propose exact and approximation techniques that offer the top-k most similar trajectories with respect to a query trajectory within a given time interval in an efficient way. We also investigate how our ideas can be applied to similar behavior of the tourists, so as to offer a high-quality prediction of their next movements.