Monitoring Regular Expressions on Out-of-Order Streams
Theodore J. Johnson, S. Muthukrishnan, Irina Rozenbaum · 2007
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.