Mathematics (Oct 2024)

Order-Preserving Pattern Matching with Partition

  • Joong Chae Na,
  • Youngjoon Kim,
  • Seokchul Kang,
  • Jeong Seop Sim

DOI
https://doi.org/10.3390/math12213381
Journal volume & issue
Vol. 12, no. 21
p. 3381

Abstract

Read online

Order-preserving pattern matching, which considers the relative orders of strings, can be applied to time-series data analysis. To perform a more meaningful analysis of time-series data, approximate criteria for the order-isomorphism are necessary, considering diverse types of errors. In this paper, we introduce a novel approximation criterion for the order-isomorphism, called the partitioned order-isomorphism. We then propose an efficient O(n+sort(m))-time algorithm for the order-preserving pattern matching problem considering the criterion of partition. A comparative experiment demonstrates that the proposed algorithm is more effective than the exact order-preserving pattern matching algorithm.

Keywords