TY  - JOUR
T1  - Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm
AU  - Park, Kyung Bin 
AU  - Kim, Youngho 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2021
DA  - 2021/1/14
DO  - 10.5626/JOK.2021.48.3.249
KW  - GPU
KW  - order-preserving multiple pattern matching
KW  - Karp-Rabin algorithm
KW  - parallel implementation
AB  - 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<SUB>k</SUB>}, 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.