Regular Expression Pattern Matching with Sliding Windows cover Probabilistic Event Streams

As smartphones and IoT devices become widespread, event streams, which are continuous analysis results of sensing data, have received a Iot of attention. When we consider the utilization of event streams, it is important to deal with probabilistic event streams due to the noises of sensing data and the limitation of analysis techniques. Although existing methods proposed the monitoring of time series events with regular expressions, there is no efficient method to calculate the occurrence probabilities of time series events with a sliding window. That is, existing methods cannot answer a query such as “does the specified time series event occur in last w time steps?” efficiently. Thus, in this paper, we propose an efficient calculation method by using a deterministic finite automaton (DFA). To calculate occurrence probabilities efficiently, our method divide a window into chunks and reuse the previous calculation results. Besides, we apply lazy evaluation to solve the state explosion problem of a DFA. Experimental results using real and synthetic datasets demonstrate effectiveness and efficiency of our approach.