Fast and Exact Monitoring of Co-Evolving Data Streams
Authors:
- Yasuko MatsubaraYMYasuko Matsubara
- Yasushi SakuraiYSYasushi Sakurai
- Naonori UedaNUNaonori Ueda
- Masatoshi YoshikawaMYMasatoshi Yoshikawa
- 1 December 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 390-399
Abstract
Given a huge stream of multiple co-evolving sequences, such as motion capture and web-click logs, how can we find meaningful patterns and spot anomalies? Our aim is to monitor data streams statistically, and find sub sequences that have the characteristics of a given hidden Markov model (HMM). For example, consider an online web-click stream, where massive amounts of access logs of millions of users are continuously generated every second. So how can we find meaningful building blocks and typical access patterns such as weekday/weekend patterns, and also, detect anomalies and intrusions? In this paper, we propose Stream Scan, a fast and exact algorithm for monitoring multiple co-evolving data streams. Our method has the following advantages: (a) it is effective, leading to novel discoveries and surprising outliers, (b) it is exact, and we theoretically prove that Stream Scan guarantees the exactness of the output, (c) it is fast, and requires O (1) time and space per time-tick. Our experiments on 67GB of real data illustrate that Stream Scan does indeed detect the qualifying subsequence patterns correctly and that it can offer great improvements in speed (up to 479,000 times) over its competitors.Keywords
This publication has 30 references indexed in Scilit:
- Finding semantics in time series2011
- Optimal Distance Bounds on Time-Series Data2009
- Access Methods for Markovian Streams2009
- BRAID2005
- Elastic Translation Invariant Matching of TrajectoriesMachine Learning, 2005
- Prediction and indexing of moving objects with unknown motion patterns2004
- Indexing Large Human-Motion Databases2004
- Application of hidden Markov models for recognition of a limited set of words in unconstrained speech2003
- An online algorithm for segmenting time series2002
- Automatic recognition of keywords in unconstrained speech using hidden Markov modelsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1990