Humboldt-Universität zu Berlin

A time series is a sequence of real valued numbers ordered in time. Motif discovery is the problem of finding frequently occurring patterns,  so-called motifs, in a time series. This fundamental problem is used  across many domains, such as medicine, biology, meteorology and  robotics. In literature, multiple motif definitions are foundfinding the top latent motif, i.e. with highest number of occurrences, has received a lot of attention in recent research, its complexity is still unknown. In this work, we show that it is NP complete.

Furthermore, the motif length is a parameter that is hard to determine in practical applications. However, state-of-the-art algorithms for latent motif discovery either require the length to be set explicitly or they find approximate results. In this work, we propose VLCM, which is the first exact algorithm that discovers latent motifs of variable length and thus eliminates the need to accurately set the motif length. Our algorithm solves the top latent motif discovery problem by reducing it to the maximum clique problem. To find motifs of variable length, VLCM computes the top latent motif for each length in a given range. A naive method would run a state-of-the-art fixed-length algorithm once for each length. We use multiple pruning techniques to greatly reduce the number of calculations needed. This results in VLCM being an order of magnitude faster than the naive approach.

In our evaluation we compare our algorithm against state-of-the-art methods in terms of runtime, memory consumption and motif quality. The results show that VLCM processes time series up to length 60‘000 within one hour, while having a memory consumption of less than 6 GiB. The algorithm also finds the highest quality motifs. First, VLCM’s motifs contain 2 to 10 times as many occurrences as approximate methods given the same similarity threshold. Second, it has the highest accuracy across all state-of-the-art methods when analyzing motifs found on datasets with annotated ground-truth motifs.

Deutsche Version

Eine Zeitreihe ist eine zeitlich geordnete Folge reeller Zahlen. „Motif Discovery“ ist das Problem, häufig vorkommende Muster, sogenannte Motive, in einer Zeitreihe zu finden. Dieses grundlegende Problem wird in vielen Bereichen verwendet, bspw. der Medizin, Biologie, Meteorologie und Robotik. In der Literatur finden sich mehrere Motivdefinitionen.

In dieser Arbeit sollen latente Motive gefunden werden, bei denen sich die Vorkommen nur approximativ ähneln müssen. Obwohl das Finden des besten latenten Motivs, also mit der höchsten Anzahl an Vorkommen, in jüngster Forschung viel Aufmerksamkeit erhalten hat, ist seine Komplexität noch unbekannt. In dieser Arbeit wird bewiesen, dass es zu der Klasse der NP-vollständigen Probleme gehört.

Weiterhin ist die Motivlänge ein Parameter, der in praktischen Anwendungen schwer zu bestimmen ist. Moderne Algorithmen zur Erkennung latenter Motive erfordern jedoch entweder die explizite Angabe der Länge oder sie finden nur ungenaue Ergebnisse. In dieser Arbeit wird VLCM vorgestellt: der erste exakte Algorithmus, der latente Motive variabler Länge findet. Dadurch beseitigt er die Notwendigkeit, die Motivlänge genau einzustellen. Der Algorithmus findet das beste latente Motiv, indem er es das Problem auf das Finden der maximalen Clique in einem speziellen konstruierten Graphen zurückführt. Um Motive variabler Länge zu finden, berechnet VLCM das beste latente Motiv für jede Länge in einem gegebenen Intervall. Ein naives Verfahren würde einen aktuellen Algorithmus mit fester Länge je einmal für jede Länge ausführen. VLCM verwendet jedoch mehrere Pruning-Techniken, um die Anzahl der erforderlichen Berechnungen erheblich zu reduzieren. Dies führt dazu, dass VLCM um das Zehnfache schneller ist als der naive Ansatz.

In der Auswertung wird der Algorithmus hinsichtlich Laufzeit, Speicherverbrauch und Motivqualität mit den modernsten Methoden verglichen. Die Ergebnisse zeigen, dass VLCM Zeitreihen bis zu einer Länge von 60‘000 innerhalb einer Stunde verarbeitet, wobei weniger als 6 GiB Arbeitsspeicher verbraucht werden. Der Algorithmus findet zudem die hochwertigsten Motive. Zunächst enthalten die Motive von VLCM 2- bis 10-mal so viele Vorkommen wie andere Verfahren. Außerdem zeigt VLCM die höchste Genauigkeit beim Finden des besten latenten Motivs.