Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching

Youkun Shin, Youngho Kim, Jeong Seop Sim

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

Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T which are order-isomorphic to P. Given a text T of length n and a set of patterns W={P₁, P₂,…, P_b}, the order-preserving multiple pattern matching problem is to find all substrings in T which are order-isomorphic to patterns of W. In this paper, we present two parallel algorithms based on the Z-function. The first algorithm for the order-preserving pattern matching problem runs in O(m) time using O(n+hm) threads and the second algorithm for the order-preserving multiple pattern matching problem runs in O(n+M) time using O(b(n+M)) threads, where h is the number of blocks and M is the length of the longest pattern in W. Experimental results show that our parallel algorithm for the order-preserving pattern matching problem is approximately 71.2 times faster than the sequential algorithm when m=10 and n=1,000,000, and that our parallel algorithm for the order-preserving multiple pattern matching problem is approximately 12.2 times faster than the sequential algorithm when b=1,000, m=10, and n=1,000.