Regular Expression Filtering on Multiple q-Grams

Seon-Ho SHIN
HyunBong KIM
MyungKeun YOON

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D    No.1    pp.253-256
Publication Date: 2018/01/01
Publicized: 2017/10/11
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017EDL8180
Type of Manuscript: LETTER
Category: Information Network
regular expression,  string matching,  q-gram,  intrusion detection,  deep packet inspection,  

Full Text: PDF(282KB)>>
Buy this Article

Regular expression matching is essential in network and big-data applications; however, it still has a serious performance bottleneck. The state-of-the-art schemes use a multi-pattern exact string-matching algorithm as a filtering module placed before a heavy regular expression engine. We design a new approximate string-matching filter using multiple q-grams; this filter not only achieves better space compactness, but it also has higher throughput than the existing filters.

open access publishing via