Monitoring regular expressions on out-of-order streams

Theodore Johnson, S. Muthukrishnan, Irina Rozenbaum

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


    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 - 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

    ASJC Scopus subject areas

    • Software
    • Signal Processing
    • Information Systems


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

    Cite this