Multiple Regular Expression Pattern Monitoring over Probabilistic Event Streams

Kento SUGIURA  Yoshiharu ISHIKAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.5   pp.982-991
Publication Date: 2020/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019DAP0009
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)
Category: 
Keyword: 
probabilistic event streams,  regular expressions,  pattern matching,  sliding windows,  

Full Text: PDF(869.1KB)>>
Buy this Article




Summary: 
As smartphones and IoT devices become widespread, probabilistic event streams, which are continuous analysis results of sensing data, have received a lot of attention. One of the applications of probabilistic event streams is monitoring of time series events based on regular expressions. That is, we describe a monitoring query such as “Has the tracked object moved from RoomA to RoomB in the past 30 minutes?” by using a regular expression, and then check whether corresponding events occur in a probabilistic event stream with a sliding window. Although we proposed the fundamental monitoring method of time series events in our previous work, three problems remain: 1) it is based on an unusual assumption about slide size of a sliding window, 2) the grammar of pattern queries did not include “negation”, and 3) it was not optimized for multiple monitoring queries. In this paper, we propose several techniques to solve the above problems. First, we remove the assumption about slide size, and propose adaptive slicing of sliding windows for efficient probability calculation. Second, we calculate the occurrence probability of a negation pattern by using an inverted DFA. Finally, we propose the merge of multiple DFAs based on disjunction to process multiple queries efficiently. Experimental results using real and synthetic datasets demonstrate effectiveness of our approach.