Physical Sciences and Mathematics Commons^™

On Discovering Motifs And Frequent Patterns In Spatial Trajectories With Discrete Fréchet Distance, Bo Tang, Man Lung Yiu, Kyriakos Mouratidis, Jiahao Zhang, Kai Wang

Research Collection School Of Computing and Information Systems

The discrete Fréchet distance (DFD) captures perceptual and geographical similarity between two trajectories. It has been successfully adopted in a multitude of applications, such as signature and handwriting recognition, computer graphics, as well as geographic applications. Spatial applications, e.g., sports analysis, traffic analysis, etc. require discovering similar subtrajectories within a single trajectory or across multiple trajectories. In this paper, we adopt DFD as the similarity measure, and study two representative trajectory analysis problems, namely, motif discovery and frequent pattern discovery. Due to the time complexity of DFD, these tasks are computationally challenging. We address that challenge with a suite of …