Accelerating Sequence Operator with Reduced Expression

Hideyuki Kawashima, Osamu Tatebe

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Sequence operators are effective for efficiently combining multiple events when state recognition is performed by combining time series events. Since sensor data are inherently noisy, one can take a strict attitude to deal with them: It is conceivable that all of time series events are regarded as false positives. Then, all complex events should be constructed carefully. Such an attitude is called the skip-till-any-match model in the sequence operator. When using this model, huge amounts of potential complex events are generated. A sequence operator usually supports both Kleene closure and non-Kleene closure. While efficient methods have been studied for Kleene closure so far, that for non-Kleene closure have been still explored. In this paper, we propose the reduced expression method to improve the efficiency of sequence operator processing for the skip-till-any-match model. Experimental results showed that the processing time and memory size were more efficient compared with SASE, which is the conventional method, and that degree is up to several thousand times.

Original languageEnglish
Title of host publicationInformation Modelling and Knowledge Bases XXXI
EditorsAjantha Dahanayake, Janne Huiskonen, Yasushi Kiyoki, Bernhard Thalheim, Hannu Jaakkola, Naofumi Yoshida
PublisherIOS Press BV
Number of pages12
ISBN (Electronic)9781643680446
Publication statusPublished - 2019 Dec 13
Event29th International Conference on Information Modeling and Knowledge Bases, EJC 2019 - Lappeenranta, Finland
Duration: 2019 Jun 32019 Jun 7

Publication series

NameFrontiers in Artificial Intelligence and Applications
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314


Conference29th International Conference on Information Modeling and Knowledge Bases, EJC 2019


  • Complex event processing
  • Data stream
  • Sequence operator

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Accelerating Sequence Operator with Reduced Expression'. Together they form a unique fingerprint.

Cite this