Regular Expression Filtering on Multiple q-Grams

Seon-Ho SHIN  HyunBong KIM  MyungKeun YOON  

Publication
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
Keyword: 
regular expression,  string matching,  q-gram,  intrusion detection,  deep packet inspection,  

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




Summary: 
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.