Automatic Detection of Warped Patterns in Time Series: The Caterpillar Algorithm

摘要

Detection of similar representations of a given query time series within longer time series is an important task in many applications such as finance, activity research, text mining and many more. Identifying time warped instances of different lengths but similar shape within longer time series is still a difficult problem. We propose the novel Caterpillar algorithm which fuses the advantages of Dynamic Time Warping (DTW) and the Minimum Description Length (MDL) principle to move a sliding window in a crawling-like way into the future and past of a time series. To demonstrate the wide field of application and validity, we compare our method against stateof-the-art methods on accelerometer time series and synthetic random walks. Our experiments demonstrate that Caterpillar outperforms the comparison methods in detecting accelerometer signals of metro stops.