Not logged in.

Quick Search - Contribution

Contribution Details

Type Master's Thesis
Scope Discipline-based scholarship
Title Exhaustive enumeration of variable-length motifs in time series
Organization Unit
Authors
  • Laura Toedtli
Supervisors
  • Michael Hanspeter Böhlen
Language
  • English
Institution University of Zurich
Faculty Faculty of Business, Economics and Informatics
Date 2022
Abstract Text Motifs are recurring patterns in a time series at varying lengths. This thesis presents two problem definitions to find such relevant motifs in time series: Finding the K-most similar motif pairs for a given length range and finding all strongly correlated motif pairs for a given length range. In order to solve the posed problems, we present exact algorithms for either problem. We present three brute force algorithms that can be adapted to solve either problem and the exact pruning algorithms motif enumerator (MOEN), which solves the 1-most similar motif pair problem. In this thesis, we evaluate the pruning algorithm's scalability compared to its fastest brute force counterpart, evaluate how the correlation threshold influences the run time and compare the types of recurring motifs that the different algorithms can discover.
Zusammenfassung Motive sind wiederkehrende Muster mit unterschiedlichen Längen in einer Zeitreihe. In dieser Arbeit stellen wir zwei Problemstellungen vor, um solche relevanten Motive in Zeitreihen zu finden: Die Suche nach den K-ähnlichsten Motivpaaren für einen gegebenen Längenbereich und die Suche nach allen stark korrelierten Motivpaaren für einen gegebenen Längenbereich. Um die definierten Probleme zu lösen, stellen wir exakte Algorithmen für beide Probleme vor. Wir stellen drei Brute-Force-Algorithmen vor, die zur Lösung beider Probleme angepasst werden können, sowie die exakten Pruning-Algorithmen motif enumerator (MOEN), der das Problem der 1-ähnlichsten Motivpaaren löst. In dieser Arbeit evaluieren wir die Skalierbarkeit der Pruning-Algorithmen im Vergleich zu ihren schnellsten Brute-Force-Pendants, bewerten, wie die Korrelationsschwelle die Laufzeit beeinflusst, und vergleichen die Arten von wiederkehrenden Motiven, die die verschiedenen Algorithmen entdecken können.
PDF File Download
Export BibTeX