A motif is a pair of non-overlapping sequences with very
similar shapes in a time series. We study the online top-
k most similar motif discovery problem. A special case of
this problem corresponding to k = 1 was investigated in
the literature by Mueen and Keogh [2]. We generalize the
problem to any k and propose space-ecient algorithms for
solving it. We show that our algorithms are optimal in term
of space. In the particular case when k = 1, our algorithms
achieve better performance both in terms of space and time
consumption than the algorithm of Mueen and Keogh. We
demonstrate our results by both theoretical analysis and
extensive experiments with both synthetic and real-life data.
We also show possible application of the top-k similar motifs
discovery problem.
