Scalable Regular Expression Matching on Data Streams

Summary: End-to-end high-performance RE matching on data streams by marrying DFA throughput with NFA space efficiency. Core ideas: cache the frequent DFA states, cluster interacting REs to cap state blowup, enabling scalable matching under tight memory and outperforming a leading IDS. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4047
Venue: SIGMOD
Year: 2008
Pagerank: 6.7290402e-05
Overall Rank: 4,391 | 69.88%
DOI: 10.1145/1376616.1376635

Incoming Non-self Citations Over Time

Authors

1. Anirban Majumder (AT&T)
2. Rajeev Rastogi (Yahoo)
3. Sriram Vanama (Indian Institute of Technology Madras)

BibTeX Citation

@inproceedings{majumder_sigmod08,
        title = {{Scalable Regular Expression Matching on Data Streams}},
        author = {Majumder, Anirban and Rastogi, Rajeev and Vanama, Sriram},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376635},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376635},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,005	ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events	2009	SIGMOD	0.000126998
1,022	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.00012602841
3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB	7.4999147e-05
6,716	SigMatch: Fast and Scalable Multi-Pattern Matching	2010	VLDB	5.7958663e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
875	Towards an Internet-Scale XML Dissemination Service	2004	VLDB	0.00013478623
3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB	7.1577657e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,786	AFilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering	2006	VLDB
2	341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB
3	3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB
4	4,503	Event Pattern Matching over Graph Streams	2015	VLDB
5	9,312	REmatch: a novel regex engine for finding all matches	2023	VLDB
6	5,426	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
7	12,240	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD
8	3,342	High-Performance Dynamic Pattern Matching over Disordered Streams	2010	VLDB
9	12,299	Deterministic Regular Expressions in Linear Time	2012	PODS
10	565	Efficient Pattern Matching over Event Streams	2008	SIGMOD