An efficient parallel algorithm for exact multi‐pattern matching
Hongli Zhang, Dongliang Xu, Zhihong Tian, Yujian Fan · Security and Communication Networks · 2014
Abstract 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 intoNsubsets where the length of patterns is the same, and different subsets would not intersect each other. We construct an EBF for each subset and useNthreads 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. Copyright © 2014 John Wiley & Sons, Ltd.