Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/105688
Title: | Efficient motif discovery in spatial trajectories using discrete Fréchet distance | Authors: | Tang, B Yiu, ML Mouratidis, K Wang, K |
Issue Date: | 2017 | Source: | Advances in Database Technology - EDBT 2017 : 20th International Conference on Extending Database Technology, Venice, Italy, March 21–24, 2017, proceedings, p. 378-389 | 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. | Publisher: | OpenProceedings.org | ISBN: | 978-3-89318-073-8 | DOI: | 10.5441/002/edbt.2017.34 | Rights: | © 2017, Copyright is with the authors. Published in Proc. 20th International Conference on Extending Database Technology (EDBT), March 21-24, 2017 - Venice, Italy: ISBN 978-3-89318-073-8, on OpenProceedings.org. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0 (https://creativecommons.org/licenses/by-nc-nd/4.0/) The following publication Tang, B., Yiu, M. L., Mouratidis, K., & Wang, K. (2017). Efficient motif discovery in spatial trajectories using discrete fréchet distance. In Proc. 20th International Conference on Extending Database Technology (EDBT), March 21-24, 2017-Venice, Italy, p. 634-637 is available at https://doi.org/10.5441/002/edbt.2017.34. |
Appears in Collections: | Conference Paper |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
paper-138.pdf | 1.92 MB | Adobe PDF | View/Open |
Page views
3
Citations as of Apr 28, 2024
Downloads
1
Citations as of Apr 28, 2024
SCOPUSTM
Citations
18
Citations as of Apr 26, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.