FRM-Miner: efficient motif discovery in large collections of time series

Abstract

The discovery of repeated structures in time series, known as motifs, is an important data mining task. Various techniques exist to discover motifs within a single time series or a pair of time series, either for a user-defined motif length or a range of lengths. However, discovering motifs in larger collections of time series is given less attention to. We propose an improved version of FRM-Miner, an efficient algorithm for discovering informative patterns in collections of time series. FRM-Miner converts time series with SAX and applies frequent sequential pattern mining to the resulting symbolic sequences, after which frequent patterns are mapped back to time series occurrences. FRM-Miner discovers non-overlapping motifs that occur frequently throughout the time series database. Discovered motifs are ranked on the z-normalised euclidean distance between their occurrences. Unlike current state-of-the-art approaches, FRM-Miner finds frequent motifs sets with varying lengths and levels of support efficiently in large time series databases. We compare run time efficiency and memory requirements between different versions of the algorithm. Through extensive experimentation, we demonstrate the robustness to noise, real-world applicability, and scalability of FRM-Miner.