An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks

vldb26-2567 · Experiment, Analysis & Benchmark (EA&B) · Ling Zhang, Shaleen Deep, Jignesh Patel, Karthikeyan Sankaralingam
Abstract

Efficient evaluation of regular expressions (regex, for short) is crucial for text analysis, and n-gram indexes are fundamental to achieving fast regex evaluation performance. However, these indexes face scalability challenges because of the exponential number of possible n-grams that must be indexed. Many existing selection strategies, developed decades ago, have not been rigorously evaluated on contemporary large-scale workloads and lack comprehensive performance comparisons. Therefore, a uni"ed and comprehensive evaluation framework is necessary to compare these methods under the same experimental settings. This paper presents the "rst systematic evaluation of three representative n-gram selection strategies across "ve workloads, including real-time production logs and genomic sequence analysis. We examine their trade-o#s in terms of index construction time, storage overhead, false positive rates, and end-to-end query performance. Through empirical results, this study provides a modern perspective on existing n-gram based regular expression evaluation methods, extensive observations, valuable discoveries, and an adaptable testing framework to guide future research in this domain. We makeourimplementations of these methods and our test framework available as open-source at https://github.com/mush-zhang/RegexIndexComparison.

Assigned reviewers

No reviewers assigned yet.

Candidates from the panel ranked by taxonomy affinity

#ReviewerMatchLoadWhy