@article{M4E230F37,
title = "Algorithms for the k-Scaled Order-Preserving Pattern Matching Problem",
journal = "Journal of KIISE, JOK",
year = "2022",
issn = "2383-630X",
doi = "10.5626/JOK.2022.49.8.585",
author = "Kyung Bin Park,Youngho Kim,Joong Cha Na,Jeong Seop Sim",
keywords = "order-isomorphism,order-preserving pattern matching,approximate order-preserving pattern matching,parallel algorithm",
abstract = "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."
}