# Order-Preserving Multiple Pattern Matching in Parallel
## 1 Introduction  
Two strings \(x,y\) (\(|x|=|y|\)) from an integer alphabet are order-isomorphic if the relative orders of characters are the same. For example, given two strings \(x=(17,30,10)\) and \(y=(4,9,1)\), they are order-isomorphic because their relative orders of characters are the same as \((2,3,1)\). Given text \(T(|T|=n)\) and pattern \(P(|P|=m)\), finding all substrings of \(T\), which are order-isomorphic to \(P\), is called the order-preserving pattern matching (OPPM for short) problem [1; 2; 3; 4; 5]. Given text \(T(|T|=n)\) and a set of patterns \(\mathbb{P}=\{P_{1},\ldots,P_{k}\}\), the order-preserving multiple pattern matching (OPMPM for short) problem is to find all substrings of \(T\) that are order-isomorphic to any \(P_{a}(1\leq a\leq k)\) in \(\mathbb{P}\)[1; 2; 3; 4; 5]. The order-preserving pattern matching problem and order-preserving multiple pattern matching problem can be used to analyze various time-series data such as stock price indices, music melodies, and biomedical data [1; 2; 3; 4; 5].  
Most existing OPMPM algorithms are performed in two phases: a preprocessing phase and a search phase. Let \(m\), \(\overline{m}\), and \(M\) denote the shortest pattern length, the longest pattern length, and the sum of the lengths of all patterns in \(\mathbb{P}\), respectively. [PERSON] et al. [1] proposed an algorithm that performs the preprocessing phase in \(O(M\log\overline{m})\) time and the search phase in \(O(n\log\overline{m})\) time using Aho-Corasick automata [6]. [PERSON] et al. [7] proposed two algorithms for the order-preserving multiple pattern matching problem. In the first algorithm, the preprocessing and search phases run in \(O(kmq+M\log\overline{m})\) time and \(O((n/m)\log M)\) time, on average, and in the second algorithm, the preprocessing and search phases run in \(O(M\log\overline{m})\) time and \(O(n)\) time, on average. [PERSON] et al. [8] proposed an algorithm that improved the space complexity of the first algorithm proposed in [7] from \(O(q!+k+M)\) to \(O(k+M)\) using fingerprint tables. [PERSON] et al. [9] parallelized the second algorithm proposed in [7]. The preprocessing phase runs in \(O(\overline{m})\) time using \(O(M)\) threads and the search phase runs in \(O(m)\) time, on average, using \(O(n)\) threads in [9].  
In this paper, we present two parallel algorithms for the OPMPM problem. First, we parallelize the algorithm proposed in [1]. The preprocessing phase of the first algorithm runs in \(O(\overline{m})\) time using \(O(M)\) threads and the search phase runs in \(O(\overline{m}\log\overline{m})\) time using \(O(n/\overline{m})\) threads. Second, we parallelize the algorithm proposed in [8]. The preprocessingphase of the second algorithm runs in \(O(\overline{m})\) time using \(O(M)\) threads and the search phase runs in \(O(M)\) time using \(O(n)\) threads. Then, we present experimental results that compare the execution times of each parallel algorithm for various types of time-series data. The experimental results showed that for randomly generated strings, when \(n=100\),000, \(m=9\), and \(k=100\), the execution time of the first parallel algorithm was approximately \(2.12\) times faster than the sequential algorithm, and the second parallel algorithm was approximately \(1.6\) times faster than the sequential algorithm. For all time-series data used in our experiments, the execution time of our second parallel algorithm was comparable to that of a fast parallel algorithm proposed in [9].  
This paper is organized as follows. In Section 2, we introduce the definitions of terms and related studies. In Section 3, we explain our parallel algorithms for the OPMPM problem. In Section 4, the execution times of parallel algorithms are compared through experiments. In Section 5, we conclude.