An efficient parallel algorithm for exact multi-pattern matching

作者：Zhang Hongli; Xu Dongliang^*; Tian Zhihong; Fan Yujian

来源：Security and Communication Networks, 2015, 8(9): 1688-1697.

DOI：10.1002/sec.1115

• multi-pattern matching
• parallel matching
• Bloom Filter
• GPU

This paper presents a parallel algorithm Parallel Extended Bloom Filter (PEBF) for exact multi-pattern matching based on Bloom filter. To improve the throughput and parallelism of the algorithm, we divided the pattern set into N subsets where the length of patterns is the same, and different subsets would not intersect each other. We construct an EBF for each subset and use N threads to simultaneously process the subsets in parallel. We implement our solution on the graphics processing unit, called G-PEBF. Experimental results demonstrate that PEBF performs better than the Wu-Manber (WM) algorithm in terms of time and space. And G-PEBF outperforms the G-WM (WM algorithm implemented on graphics processing unit). The speedup of G-PEBF is up to 60 times at peak performance and almost 10 times at worst performance to the PEBF algorithm.

• 出版日期2015-6
• 单位哈尔滨工业大学