Order-Preserving Pattern Matching with Partition
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,...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/12/21/3381 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846173310750031872 |
|---|---|
| author | Joong Chae Na Youngjoon Kim Seokchul Kang Jeong Seop Sim |
| author_facet | Joong Chae Na Youngjoon Kim Seokchul Kang Jeong Seop Sim |
| author_sort | Joong Chae Na |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>+</mo><mi>s</mi><mi>o</mi><mi>r</mi><mi>t</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>)</mo></mrow></semantics></math></inline-formula>-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. |
| format | Article |
| id | doaj-art-58eb83f023484d49b132e90a844c86fd |
| institution | Kabale University |
| issn | 2227-7390 |
| language | English |
| publishDate | 2024-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-58eb83f023484d49b132e90a844c86fd2024-11-08T14:37:43ZengMDPI AGMathematics2227-73902024-10-011221338110.3390/math12213381Order-Preserving Pattern Matching with PartitionJoong Chae Na0Youngjoon Kim1Seokchul Kang2Jeong Seop Sim3Department of Computer Science and Engineering, Sejong University, Seoul 05006, Republic of KoreaDepartment of Computer Engineering, Inha University, Incheon 22212, Republic of KoreaDepartment of Computer Engineering, Inha University, Incheon 22212, Republic of KoreaDepartment of Computer Engineering, Inha University, Incheon 22212, Republic of KoreaOrder-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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>+</mo><mi>s</mi><mi>o</mi><mi>r</mi><mi>t</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>)</mo></mrow></semantics></math></inline-formula>-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.https://www.mdpi.com/2227-7390/12/21/3381order-preserving pattern matchingapproximate order-preserving pattern matchingpattern matching with partitionstring matching |
| spellingShingle | Joong Chae Na Youngjoon Kim Seokchul Kang Jeong Seop Sim Order-Preserving Pattern Matching with Partition Mathematics order-preserving pattern matching approximate order-preserving pattern matching pattern matching with partition string matching |
| title | Order-Preserving Pattern Matching with Partition |
| title_full | Order-Preserving Pattern Matching with Partition |
| title_fullStr | Order-Preserving Pattern Matching with Partition |
| title_full_unstemmed | Order-Preserving Pattern Matching with Partition |
| title_short | Order-Preserving Pattern Matching with Partition |
| title_sort | order preserving pattern matching with partition |
| topic | order-preserving pattern matching approximate order-preserving pattern matching pattern matching with partition string matching |
| url | https://www.mdpi.com/2227-7390/12/21/3381 |
| work_keys_str_mv | AT joongchaena orderpreservingpatternmatchingwithpartition AT youngjoonkim orderpreservingpatternmatchingwithpartition AT seokchulkang orderpreservingpatternmatchingwithpartition AT jeongseopsim orderpreservingpatternmatchingwithpartition |