Publication Type

Conference Proceeding Article

Publication Date

3-2017

Abstract

The discrete Fréchet distance (DFD) captures perceptual and geographicalsimilarity between discrete trajectories. It has been successfullyadopted in a multitude of applications, such as signatureand handwriting recognition, computer graphics, as well as geographicapplications. Spatial applications, e.g., sports analysis,traffic analysis, etc. require discovering the pair of most similarsubtrajectories, 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 computationalcomplexity of DFD calculation. In this paper, we propose asuite of novel lower bound functions and a grouping-based solutionwith multi-level pruning in order to compute motifs with DFD ef-ficiently. Our techniques apply directly to motif discovery withinthe same or between different trajectories. An extensive empiricalstudy on three real trajectory datasets reveals that our approach is 3orders of magnitude faster than a baseline solution.

Discipline

Categorical Data Analysis | Data Storage Systems

Research Areas

Data Management and Analytics

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

EDBT

City or Country

Venice, Italy

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

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

Share

COinS