Kyung Bin Park  Youngho Kim  Joong Cha Na  Jeong Seop Sim

10.5626/JOK.2022.49.8.585

order-isomorphism order-preserving pattern matching approximate order-preserving pattern matching Parallel algorithm

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.