Pattern Matching with Adaptive Granularity Over Streaming Time Series
Rong Kang, Chen Wang, Peng Wang, Yuting Ding, Jianmin Wang · arXiv (Cornell University) · 2017
Processing of streaming time series data from sensors with lower latency and limited computing resource comes to a critical problem as the growth of Industry 4.0 and Industry Internet of Things. To tackle the real world challenge in this area, we formulate a new problem, called fine-grained pat- tern matching. It allows users to define varied deviations to different segments of a given pattern, and adaptive breakpoint of adjunct segments, which urges the dramatically increased complexity against traditional pattern matching problem over stream. In this paper, we propose a novel approach to solve this problem. In the pruning phase, we propose Equal Length Block(ELB) representation and Block- Skipping Pruning(BSP) policy, which guarantees low cost feature calculation, efficient pruning and no false dismissals. In the post-processing phase, a delta-function is proposed to en- able us to conduct exact matching and determine the adaptive breakpoint in linear complexity. Extensive experiments are evaluated on synthetic and real-world datasets, which illustrates that our algorithm outperforms the brute-force method and MSM, a multi-step filter mechanism over the multi-scaled representation, by orders of magnitude.