HIME: discovering variable-length motifs in large-scale time series

摘要

Detecting repeated variable-length patterns, also called variable-length motifs, has received a great amount of attention in recent years. The state-of-the-art algorithm utilizes a fixed-length motif discovery algorithm as a subroutine to enumerate variable-length motifs. As a result, it may take hours or days to execute when the enumeration range is large. In this work, we introduce an approximate algorithm called hierarchical-based motif enumeration (HIME) to detect variable-length motifs with a large enumeration range in million-scale time series. We show in the experiments that the scalability of the proposed algorithm is significantly better than that of the state-of-the-art algorithm. Moreover, the motif length range detected by HIME is considerably larger than previous sequence matching-based approximate variable-length motif discovery approach. We demonstrate that HIME can efficiently detect meaningful variable-length motifs in long, real-world time series.