# Order-Preserving Multiple Pattern Matching in Parallel
## 4 Experimental Results  
The experiment was conducted on the following environment: Windows 10 (64-bit) operating system, AMD Ryzen9 3950X CPU, 64 GB RAM, NVIDIA GeForce RTX 3080 Ti GPU, C++ and CUDA programming language, and Visual Studio 2019 (CUDA SDK 11.0). The algorithms experimented with in the present paper are denoted as follows: The OPMPM algorithm using the Aho-Corasick automaton proposed in [1] is denoted by \(AC\), and the OPMPM algorithm using the fingerprint table proposed in [8] is denoted by \(FT\). The parallel OPMPM algorithm proposed in [9] is denoted by \(pKR\), the parallel OPMPM algorithm using the Aho-Corasick automaton proposed in this paper is denoted by \(pAC\), and the parallel OPMPM algorithm using the fingerprint table is denoted by \(pFT\), respectively. The data used in the experiment are randomly generated strings and two types of time-series data: the Dow Jones Index and electrocardiogram data. * Randomly generated strings: Texts and patterns consisting of \(\sum=\left\{1,2,\ldots,2^{30}\right\}\) were randomly generated. Text \(T\) was generated by increasing length \(n\) from 10,000 by 10,000 to 100,000. A set of patterns \(P\) was generated by increasing the number of patterns \(k\) from 100 by 100 to 1000 and increasing the pattern length \(m\) from 5 by 1 to 15. * Dow Jones Index: Texts and patterns were extracted at random for each experiment from the daily closing price of the Dow Jones Industrial Average between 2 May 1885 and 12 April 2019 [14]. The text length \(n\) was increased from 1000 by 1000 to 10,000. The number of patterns \(k\) and their length \(m\) were set to the same values used for the randomly generated strings. * Electrocardiogram data: The electrocardiogram (ECG) data used in the experiment were obtained from the MIT-BIH ECG biosignal database provided by Physionet [15]. An electrocardiogram records the electrical impulses from the heart. Texts were randomly extracted from the total records, while patterns were extracted evenly from abnormal symptom data and normal data. It should be noted that the texts and patterns were extracted from electrocardiogram data of different individuals. The text length \(n\) and the number of patterns \(k\) were set equal to those of the randomly generated strings, and the pattern length \(m\) increased from 10 by 1 to 15 during the generation process. The parameter setup of the algorithm and measurement of execution time were conducted as follows: In \(FT\) and \(pFT\), \(q\) was set to 5. In each of the parallel algorithms, \(pAC\) employed 1000 threads, and \(pKR\) and \(pFT\) employed \(n\) threads. The execution time of each algorithm was the mean of 100 execution times, which was measured in milliseconds (ms) and rounded to three decimal places. The execution time of parallel algorithms includes the execution time of the cudaMemcpy() function that copies data between host memory and device (GPU) memory. Experiment (1). Comparison of execution times of \(AC\) and \(pAC\), and \(FT\) and \(pFT\) for randomly generated strings: Figure 3 shows the execution times of \(AC\) and \(pAC\) for randomly generated strings according to \(n\) when \(m=9\) and \(k=100\). When \(n=10\),000, \(pAC\) was slower than \(AC\) due to the additional execution time required by the cudaMemcpy() function in \(pAC\). Most of the execution time for \(pAC\) was spent on the cudaMemcpy() function. However, for \(n\geq 20\),000, \(pAC\) performed faster than \(AC\). When \(n=100\),000, \(m=9\), and \(k=100\), the execution time of \(AC\) was around 41.22 ms and that of \(pAC\) was around 19.49 ms, indicating that \(pAC\) was approximately 2.12 times faster than \(AC\). The execution time of \(pAC\) increased as \(n\) increased due to the limitation of the number of available GPU cores. Figure 4 shows the execution times of \(AC\) and \(pAC\) for randomly generated strings according to \(k\) when \(n=100\),000 and \(m=9\). In this case, \(pAC\) was faster than \(AC\) in all cases.