Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2022

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.

Keywords

Discrete Fréchet distance, Spatial trajectory, Trajectory analysis

Discipline

Numerical Analysis and Scientific Computing | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Publication

GeoInformatica

Volume

26

Issue

1

First Page

29

Last Page

66

ISSN

1384-6175

Identifier

10.1007/s10707-021-00438-x

Publisher

Springer Verlag (Germany)

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/s10707-021-00438-x

Download

Share

COinS