Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm

Kyung Bin Park, Youngho Kim, Jeong Seop Sim

http://doi.org/10.5626/JOK.2021.48.3.249

When two strings of the same length have the same relative orders, they are called order-isomorphic. Given a text T(｜T｜=n)and a set of patterns P̃={P₁,P₂,...,P_k}, the order-preserving multiple pattern matching problem is to find all substrings of T that are order-isomorphic to any pattern in P̃ . Let m be the length of the shortest pattern, m̅ be the length of the longest pattern, and M be the sum of lengths of all the patterns in P̃. When M is polynomial with respect to m, an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm was presented whose searching step runs in O(n) time on average. In this paper, we implemented an order-preserving multiple pattern matching algorithm using the Karp-Rabin algorithm in parallel. It runs in O(m̅) time on average using O(M) threads in the preprocessing step and runs in O(m) time on average using O(n) threads in the searching step. The experimental results for random strings as input showed that our parallel implementation performed approximately 201.5 times faster than the existing sequential algorithm when n=1,000,000, k=1,000, m=5.