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 output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)29-66
JournalGeoInformatica
DOIs
Publication statusPublished - Jun 2021

Keywords

  • Discrete Fréchet distance
  • Spatial trajectory
  • Trajectory analysis

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Information Systems

Cite this