3-Partition Order-Preserving Pattern Matching
Mathematics · 24.12.2025 · 14 (1) · 65
DOI: 10.3390/math14010065 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 24.12.2025. Verfasst von Joong Chae Na und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministry of Science and ICT.
Abstract (Originalsprache)
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.
Förderung
- Ministry of Science and ICT
Zitieren
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