Abstract—Pattern matching is an important process in various applications such as information and network security, bioinformatics, image processing, etc. Aho-Corasick (AC) is one of the most representative algorithms for multiple pattern matching. As the data becomes extraordinarily large, GPUs have been adopted to accelerate pattern matching because of their great power for parallel computing. However, if the automata of AC algorithm contains more than hundreds of thousands of nodes, its State Transition Table (STT) takes up quite large storage space which is beyond GPU memory. In this paper, we present an improved AC algorithm named as STT-partition-based parallel AC (SPAC) to reduce the storage space for GPU by separating the original STT into two parts, one is kept in GPU and the other is stored in CPU. GPU is in charge for the major filtering task in the first step and then the relatively small-scale filtered results are further processed on CPU. Experiments are carried out on three different datasets and results show that our method reduces the storage space by 45%~50% compared with state-of-the-art algorithms with comparable matching speed.

Index Terms—Aho-Corasick, GPGPU, parallel pattern matching, STT-partition.

Xudong Liu and Jian Li are with the School of Computer, Beijing University of Posts and Telecommunications, Beijing, China.
Yanbing Liu, Jing Yu and Jianlong Tan are with the Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China.

Cite:Xudong Liu, Yanbing Liu, Jian Li, Jing Yu, Jianlong Tan, "A STT-Partition-Based Parallel Algorithm for Pattern Matching on GPU and CPU," International Journal of Computer and Communication Engineering vol. 4, no. 2, pp. 90-99, 2015.