Monitoring regular expressions on out-of-order streams

Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum

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

24 Scopus citations


We present an efficient algorithm for regular expression matching on streams with out of order data, while maintaining a small state and without complete stream reconstruction. We have implemented three versions of the algorithm sequential, parallel and mixed - and show by experimental study that the algorithms are highly effective in matching regular expressions on IP packet streams.

Original languageEnglish (US)
Title of host publication23rd International Conference on Data Engineering, ICDE 2007
Number of pages5
StatePublished - Sep 24 2007
Event23rd International Conference on Data Engineering, ICDE 2007 - Istanbul, Turkey
Duration: Apr 15 2007Apr 20 2007

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other23rd International Conference on Data Engineering, ICDE 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems

Fingerprint Dive into the research topics of 'Monitoring regular expressions on out-of-order streams'. Together they form a unique fingerprint.

Cite this