Conference Proceeding Article
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.
Categorical Data Analysis | Data Storage Systems
Data Management and Analytics
Proceedings: 20th International Conference on Extending Database Technology: Advances in Database Technology EDBT 2017, Venice, Italy, 2017 March 21-24
City or Country
TANG, Bo; YIU, Man Lung; MOURATIDIS, Kyriakos; and WANG, Kai.
Efficient motif discovery in spatial trajectories using discrete fréchet distance. (2017). Proceedings: 20th International Conference on Extending Database Technology: Advances in Database Technology EDBT 2017, Venice, Italy, 2017 March 21-24. 378-389. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3633
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.