Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Verteidigung Masterarbeit: Leonard Clauß

Am Freitag, den 13.5., 13:00 Uhr wird Herr Leonard Clauß seine Masterarbeit mit dem Titel

"Variable-Length Latent Motif Discovery"



Die Verteidigung findet digital per Zoom statt. Eine Zoom-Einladung finden Sie hier. (nur mit Informatik-Account)






Motif discovery is the problem of finding frequently occurring patterns,
so-called motifs, in a time series. The problem is used across many
domains, such as medicine and robotics. We focus on finding latent
motifs, which may occur approximately in each repetition within a given
similarity threshold. The motif length typically has to be set by the
user, but it 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. Therefor, 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, resulting in a speedup of around an order of
magnitude. Our evaluation shows that, compared against state-of-the-art
algorithms, VLCM finds the highest quality motifs. It processes time
series up to length 600'000 within one hour, while having a memory
consumption of less than 6 GiB.