On discovering motifs and frequent patterns in spatial trajectories with discrete Fréchet distance

• Main Authors: TANG, Bo, YIU, Man Lung, MOURATIDIS, Kyriakos, ZHANG, Jiahao, WANG, Kai
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Discrete Fréchet distance; Spatial trajectory; Trajectory analysis; Numerical Analysis and Scientific Computing; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/6944; https://ink.library.smu.edu.sg/context/sis_research/article/7947/viewcontent/OnDiscoveringMotifsAndFrequent_av.pdf
• Institution: Singapore Management University

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 novel lower bound functions and a grouping-based solution. Our techniques apply directly when the analysis tasks are defined within the same or across multiple trajectories. An extensive empirical study on real trajectory datasets reveals that our approaches are 3 orders of magnitude faster than baseline solutions.