Multiscale Representations for Fast Pattern Matching in Stream Time Series

摘要

Similarity-based time series retrieval has been a subject of long term study due to its wide usage in many applications, such as financial data analysis and weather data forecasting. Its original task was to find those time series similar to a pattern time series data, where both the pattern and data time series are static. Recently, with an increasing demand on stream data management, similarity-based stream time series retrieval has raised new research issues due to its unique requirements during the stream processing, such as one-pass search and fast response. In this paper, we address the problem of matching both static and dynamic patterns over stream time series data. We will develop a novel multi-scale representation, called multi-scale segment mean (MSM), for stream time series data, which can be incrementally computed and thus perfectly adapted to the stream characteristics. Most importantly, we propose a novel multi-step filtering mechanism, SS, over the multi-scale representation. Analysis indicates that the mechanism can greatly prune the search space and thus offer fast response. Furthermore, batching processing optimization, the dynamic case where patterns are also from stream time series, and pattern matching over future stream time series are also discussed. Extensive experiments show the proposed scheme can efficiently filter out false candidates and detect patterns.