Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

3-2017

Abstract

The discrete Fréchet distance (DFD) captures perceptual and geographical similarity between discrete 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 the pair of most similar subtrajectories, be them parts of the same or of different input trajectories.The identified pair of subtrajectories is called a motif.The adoption of DFD as the similarity measure in motif discovery,although semantically ideal, is hindered by the high computational complexity of DFD calculation. In this paper, we propose a suite of novel lower bound functions and a grouping-based solution with multi-level pruning in order to compute motifs with DFD efficiently. Our techniques apply directly to motif discovery within the same or between different trajectories. An extensive empirical study on three real trajectory datasets reveals that our approach is 3 orders of magnitude faster than a baseline solution.

Discipline

Databases and Information Systems | Theory and Algorithms

Research Areas

Data Science and Engineering

Publication

Proceedings: 20th International Conference on Extending Database Technology: Advances in Database Technology EDBT 2017, Venice, Italy, 2017 March 21-24

First Page

378

Last Page

389

ISBN

9783893180738

Identifier

10.5441/002/edbt.2017.34

Publisher

Open Proceedings

City or Country

Konstanz, Germany

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.5441/002/edbt.2017.34

Download

Share

COinS