Efficient motif discovery in spatial trajectories using discrete fréchet distance

Bo Tang, Man Lung Yiu, Kyriakos Mouratidis, Kai Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

12 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2017
Subtitle of host publication20th International Conference on Extending Database Technology, Proceedings
Number of pages12
ISBN (Electronic)9783893180738
Publication statusPublished - 1 Jan 2017
Event20th International Conference on Extending Database Technology, EDBT 2017 - Venice, Italy
Duration: 21 Mar 201724 Mar 2017


Conference20th International Conference on Extending Database Technology, EDBT 2017

ASJC Scopus subject areas

  • Information Systems
  • Software
  • Computer Science Applications

Cite this