We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Multi-Threading and Suffix Grouping on Massive Multiple Pattern Matching Algorithm.
- Authors
Oh, Doohwan; Ro, Won W.
- Abstract
The widely used multiple pattern matching algorithms experience severe performance degradation when the number of patterns to match increases. In light of this fact, this paper presents a multi-threaded multiple pattern matching algorithm to overcome the performance degradation; this algorithm presents two additional improvements on the original Wu–Manber algorithm. First, the proposed algorithm employs a multi-threaded execution model to parallelize the pattern matching operation on multi-core processors. Second, the patterns to be searched are distributed over multiple threads according to the pattern similarity. For this purpose, the proposed algorithm groups the target patterns on the basis of their suffixes and distributes the patterns over multiple threads. Through experiments and performance analysis, our algorithm shows a significant performance gain as compared with the original Wu–Manber algorithm and the previously proposed multi-threaded pattern matching on massive pattern sets of size exceeding 5000. The results obtained from the pattern matching operation using eight cores show much improved execution time, which is nearly 14.9 times faster on average than that of the conventional Wu–Manber algorithm. It is demonstrated that the proposed idea improves the overall performance by reducing the amount of workload on a single thread through multi-threading and an efficient data distribution policy.
- Subjects
THREADS (Computer programs); PATTERN recognition systems; COMPUTER algorithms; GROUP theory; MULTICORE processors; PERFORMANCE evaluation; PARALLEL processing
- Publication
Computer Journal, 2012, Vol 55, Issue 11, p1331
- ISSN
0010-4620
- Publication type
Article