TY  - JOUR
T1  - Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem
AU  - Park, Kyung Bin 
AU  - Kim, Youngho 
AU  - Na, Joong Cha 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2022
DA  - 2022/1/14
DO  - 10.5626/JOK.2022.49.8.585
KW  - order-isomorphism
KW  - order-preserving pattern matching
KW  - approximate order-preserving pattern matching
KW  - parallel algorithm
AB  - 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.