Efficient Regular Expression Matching Based on Positional Inverted Index : (Extended Abstract)
- Resource Type
- Conference
- Authors
- Qiu, Tao; Yang, Xiaochun; Wang, Bin; Wang, Wei
- Source
- 2023 IEEE 39th International Conference on Data Engineering (ICDE) ICDE Data Engineering (ICDE), 2023 IEEE 39th International Conference on. :3859-3860 Apr, 2023
- Subject
- Computing and Processing
Automata
Data engineering
Indexes
- Language
- ISSN
- 2375-026X
We study the efficient regular expression (regex) matching problem. Existing algorithms are scanning-based algorithms that typically use an equivalent automaton compiled from the regex query to verify a document. Although some works propose various strategies to quickly jump to candidate locations in a document where a query result may appear, they still need to utilize the scanning-based method to verify these candidate locations. These methods become inefficient when there are still many candidate locations needed to be verified. In this paper, we propose a novel approach to efficiently compute all matching positions for a regex query purely based on a positional q-gram inverted index. We propose a gram-driven NFA to represent the language of a regex and show all regex matching locations can be obtained by finding positions on q-grams of GNFA that satisfy certain positional constraints. Then we propose several GNFA-based query plans to answer the query using the positional inverted index. In order to improve the query efficiency, we design the algorithm to build a tree-based query plan by carefully choosing a checking order for positional constraints. Experimental results on real-world datasets show that our method outperforms state-of-the-art methods by up to an order of magnitude in query efficiency.