Online Discovery of Top-k Similar Motifs in Time Series Data

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 algori thms 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. thms 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.