Digital Library[ Search Result ]
Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem
Kyung Bin Park, Youngho Kim, Joong Cha Na, Jeong Seop Sim
http://doi.org/10.5626/JOK.2022.49.8.585
Two strings of the same length are order-isomorphic if the relative orders of their characters are the same. Given text T of length n and pattern P of length m, the order-preserving pattern matching problem is to find all substrings of T that are order-isomorphic to P. Order-preserving pattern matching can be used to analyze time-series data such as stock indices and melodies. In this paper, we defined the k-scaled order-preserving pattern matching problem and proposed an O(n+mlogm)-time algorithm for the problem. We also proposed a parallel algorithm for the problem, which runs in O(m+k) time using O(n+m) threads.
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.
An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams
Gwangmo Yoo, Youngho Kim, Jeong Seop Sim
http://doi.org/10.5626/JOK.2018.45.11.1111
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 that have the same relative orders as P. Recently, an O(nm+nqlogq+q!)-time order-preserving pattern matching algorithm was proposed that uses fingerprints of q-grams. In this paper, we propose an order-preserving pattern matching algorithm using the fingerprints of two q-grams to improve execution times. The experimental results for randomly generated T (n = 5,000,000) and P (m = 5,10,15) show that our algorithm runs up to approximately 12% faster than the previous algorithm. Also, for T using Dow Jones Industrial Average (n = 34,658) and P (m = 5,10,15) randomly extracted from T, our algorithm runs up to approximately 10% faster than the previous algorithm.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr