Parallel Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem

Jihyo Choi, Youngho Kim, Joong Chae Na, Jeong Seop Sim

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

Given a text T(|T|= n) and a pattern P(|P|= m), the boxed-mesh permutation pattern matching problem asks to find all boxed subsequences of T that are order-isomorphic to P. In this paper we present two parallel algorithms for the problem. We first propose an O(nm) -time parallel algorithm using O(n) threads and then propose an O(n)-time algorithm using O(nm) threads. The experimental results for Daw Jones Industrial Average show that our first and second algorithms run approximately 7.2 times and 20.6 times, respectively, faster compared to the sequential algorithm using order-statistics trees when n = 36,364 and m = 30.