REmatch: a novel regex engine for finding all matches

Summary: REmatch: a regex engine implementing theoretically optimal enumeration for regexes with capture variables under all-match semantics. Introduces a new algorithm and practical optimizations to avoid naive-implementation costs, matching or beating popular engines while returning every capture match. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13122
Venue: VLDB
Year: 2023
Pagerank: 4.3849295e-05
Overall Rank: 9,157 | 36.30%
DOI: 10.14778/3611479.3611488

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,505	SuSe: Summary Selection for Regular Expression Subsequence Aggregation over Streams	2025	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,938	Split-Correctness in Information Extraction	2019	PODS	0.00010028895
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
7,398	Improving Regular-Expression Matching on Strings Using Negative Factors	2013	SIGMOD	4.7417594e-05
8,754	Efficient Enumeration for Annotated Grammars	2022	PODS	4.456315e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,951	Mining Document Collections to Facilitate Accurate Approximate Entity Matching	2009	VLDB	5.8100413e-05
10,857	An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks	2025	VLDB	4.1945683e-05
776	Efficient Pattern Matching over Event Streams	2008	SIGMOD	0.00016799754
6,958	Computational Aspects of Resilient Data Extraction from Semistructured Sources	2000	PODS	4.8857878e-05
12,042	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD	4.1945683e-05
11,240	Autonomously Computable Information Extraction	2023	VLDB	4.1945683e-05
7,398	Improving Regular-Expression Matching on Strings Using Negative Factors	2013	SIGMOD	4.7417594e-05
10,106	Regular Expression Indexing for Log Analysis	2026	SIGMOD	4.1945683e-05
4,589	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD	6.06476e-05
3,526	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB	7.0078308e-05