3-Partition Order-Preserving Pattern Matching
Mathematics · 2025-12-24 · 14 (1) · 65
DOI: 10.3390/math14010065 ↗At a glance
Journal article in Mathematics, published online on 2025-12-24. Written by Joong Chae Na and 2 co-authors. Cited 1 times so far (Crossref); 19 references. The full text is freely available (open access, CC BY 4.0). Funded by: Ministry of Science and ICT.
Abstract (original language)
Two strings of equal length are called order-isomorphic if their relative orders are identical at every position. The classical order-preserving pattern matching (OPPM) problem finds all substrings in a text T that are order-isomorphic to a pattern P. However, measurement errors can cause data loss or inaccuracies, making exact pattern detection difficult and motivating the active study of approximate OPPM variants, such as 2-partition OPPM. In this paper, we extend the existing partition-based relaxation of order-isomorphism and define the 3-partition OPPM problem. The 3-partition OPPM problem is to find all substrings in a text T that can be divided into three segments such that each partitioned segment is order-isomorphic to the corresponding segment of a pattern P. We propose an efficient algorithm to solve the problem in O(nm+m2logm) time, where n=|T| and m=|P|. We conduct experiments on various time series datasets, comparing the number of occurrences and the runtime efficiency among the OPPM, 2-partition OPPM, and proposed 3-partition OPPM algorithms. Our experimental evaluation shows that the proposed algorithm becomes increasingly cost-effective for longer patterns.
Funding
- Ministry of Science and ICT
Cite
APA
Na, J. C., Kang, S., & Sim, J. S. (2025). 3-Partition Order-Preserving Pattern Matching. Mathematics, 14(1), 65. https://doi.org/10.3390/math14010065
Vancouver
Na JC, Kang S, Sim JS. 3-Partition Order-Preserving Pattern Matching. Mathematics. 2025;14(1):65. doi:10.3390/math14010065
BibTeX
@article{Na2025,
author = {Na, Joong Chae and Kang, Seokchul and Sim, Jeong Seop},
title = {3-Partition Order-Preserving Pattern Matching},
journal = {Mathematics},
year = {2025},
volume = {14},
number = {1},
pages = {65},
doi = {10.3390/math14010065}
}
EUVIMED