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)
Incoming Non-self Citations Over Time
Authors
- 1. Xiaochun Yang
- 2. Bin Wang
- 3. Tao Qiu
- 4. Yaoshu Wang
- 5. Chen Li
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 9,157 | REmatch: a novel regex engine for finding all matches | 2023 | VLDB | 4.3849295e-05 |
Previous
Page 1 / 1
Next
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 |
|---|
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,868 | An Efficient Filter for Approximate Membership Checking | 2008 | SIGMOD | 6.6822543e-05 |
| 8,306 | Online Windowed Subsequence Matching over Probabilistic Sequences | 2012 | SIGMOD | 4.5435639e-05 |
| 12,042 | E-Matching: Event Processing over Noisy Sequences in Real Time | 2013 | SIGMOD | 4.1945683e-05 |
| 13,272 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB | - |
| 4,589 | Scalable Regular Expression Matching on Data Streams | 2008 | SIGMOD | 6.06476e-05 |
| 6,726 | A Pivotal Prefix Based Filtering Algorithm for String Similarity Search | 2014 | SIGMOD | 4.9484027e-05 |
| 9,301 | Repairing Data through Regular Expressions | 2016 | VLDB | 4.3587281e-05 |
| 9,157 | REmatch: a novel regex engine for finding all matches | 2023 | VLDB | 4.3849295e-05 |
| 7,708 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 4.6721808e-05 |
| 3,526 | RE-Tree: An Efficient Index Structure for Regular Expressions | 2002 | VLDB | 7.0078308e-05 |