An efficient parallel algorithm for exact multi-pattern matching

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.