A Graphic Processor Unit Based Multi-string Matching Algorithm for Anti-virus Systems

摘要：

String matching is a fundamental problem in computer science. Multi-string matching plays an important role in pattern recognition, search engine, virus prevention, intrusion detection and others. Aho-Corasick (AC) algorithm is a widely used multistring matching algorithm. In this paper, we present a space compacting method for AC automata based on node grouping and implement AC algorithm on GPU platform using CUDA (Computer Unified Device Architecture). We accelerate the anti-virus systems by our approach. We conduct several experiments, and our algorithm has at least 10 times of speedup of the algorithm on CPUs.

关键词： Algonthm Multi-pattern matching GPU Automaton

作者: Gongxun Qiao Zhen Wei Zhong Miao Meng Zhang

作者单位: College of Computer Science and Technology, Jilin University, Changchun, China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Engineering and Applications(2011第三届计算机工程与应用国际会议 ICCEA2011)

会议地点: 海口

会议语种:英文

页码: 324-328

在线出版日期: 2011-07-15（万方平台首次上网日期，不代表论文的发表时间）