EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

3-Partition Order-Preserving Pattern Matching

Joong Chae Na, Seokchul Kang, Jeong Seop Sim

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →