Scalable regular expression matching on data streams Export

@inproceedings{citeulike:4364983, abstract = {Regular Expression (RE) matching has important applications in the areas of XML content distribution and network security. In this paper, we present the end-to-end design of a high performance RE matching system. Our system combines the processing efficiency of Deterministic Finite Automata (DFA) with the space efficiency of Non-deterministic Finite Automata (NFA) to scale to hundreds of REs. In experiments with real-life RE data on data streams, we found that a bulk of the DFA transitions are concentrated around a few DFA states. We exploit this fact to cache only the frequent core of each DFA in memory as opposed to the entire DFA (which may be exponential in size). Further, we cluster REs such that REs whose interactions cause an exponential increase in the number of states are assigned to separate groups -- this helps to improve cache hits by controlling the overall DFA size.}, address = {New York, NY, USA}, author = {Majumder, Anirban and Rastogi, Rajeev and Vanama, Sriram}, booktitle = {SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data}, citeulike-article-id = {4364983}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1376616.1376635}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1376616.1376635}, doi = {10.1145/1376616.1376635}, isbn = {978-1-60558-102-6}, keywords = {stream}, location = {Vancouver, Canada}, pages = {161--172}, posted-at = {2009-04-19 16:21:46}, priority = {2}, publisher = {ACM}, title = {Scalable regular expression matching on data streams}, url = {http://dx.doi.org/10.1145/1376616.1376635}, year = {2008} }

TY - CONF ID - citeulike:4364983 L3 - citeulike-article-id:4364983 N2 - Regular Expression (RE) matching has important applications in the areas of XML content distribution and network security. In this paper, we present the end-to-end design of a high performance RE matching system. Our system combines the processing efficiency of Deterministic Finite Automata (DFA) with the space efficiency of Non-deterministic Finite Automata (NFA) to scale to hundreds of REs. In experiments with real-life RE data on data streams, we found that a bulk of the DFA transitions are concentrated around a few DFA states. We exploit this fact to cache only the frequent core of each DFA in memory as opposed to the entire DFA (which may be exponential in size). Further, we cluster REs such that REs whose interactions cause an exponential increase in the number of states are assigned to separate groups -- this helps to improve cache hits by controlling the overall DFA size. CY - Vancouver, Canada SN - 978-1-60558-102-6 AD - New York, NY, USA EP - 172 TI - Scalable regular expression matching on data streams PB - ACM T2 - SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data SP - 161 KW - stream AU - Majumder, Anirban AU - Rastogi, Rajeev AU - Vanama, Sriram PY - 2008/// UR - http://dx.doi.org/10.1145/1376616.1376635 ER -