Improving Regular-Expression Matching on Strings Using Negative Factors

Summary: Introduces negative factors—substrings that cannot appear in a match—to prune candidate regex matches, reducing verification while preserving completeness. Bit-parallel processing and high-quality factor selection enable integration with existing algorithms, yielding 11–74× speedups on grep-like tasks (DNA, proteins, text). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4760
Venue: SIGMOD
Year: 2013
Pagerank: 6.1170269e-05
Overall Rank: 5,698 | 60.91%
DOI: 10.1145/2463676.2465289

Incoming Non-self Citations Over Time

Authors

1. Xiaochun Yang (Northeastern University)
2. Bin Wang (Northeastern University)
3. Tao Qiu (Northeastern University)
4. Yaoshu Wang (Northeastern University)
5. Chen Li (University of California Irvine)

BibTeX Citation

@inproceedings{yang_sigmod13,
        title = {{Improving Regular-Expression Matching on Strings Using Negative Factors}},
        author = {Yang, Xiaochun and Wang, Bin and Qiu, Tao and Wang, Yaoshu and Li, Chen},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2465289},
        url = {https://dl.acm.org/doi/10.1145/2463676.2465289},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,528	Joining Extractions of Regular Expressions	2018	PODS	0.00010486718
9,312	REmatch: a novel regex engine for finding all matches	2023	VLDB	5.289545e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD
2	8,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD
3	12,240	E-Matching: Event Processing over Noisy Sequences in Real Time	2013	SIGMOD
4	13,474	On the String Matching with k Differences in DNA Databases	2021	VLDB
5	4,391	Scalable Regular Expression Matching on Data Streams	2008	SIGMOD
6	6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD
7	9,523	Repairing Data through Regular Expressions	2016	VLDB
8	9,312	REmatch: a novel regex engine for finding all matches	2023	VLDB
9	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
10	3,742	RE-Tree: An Efficient Index Structure for Regular Expressions	2002	VLDB