An Improved Order-Preserving Pattern Matching Algorithm Using Fingerprints

Youngjoon Kim, Youngho Kim and Jeong Seop Sim
Additional contact information
Youngjoon Kim: Department of Computer Engineering, Inha University, Incheon 22212, Korea
Youngho Kim: Department of Computer Engineering, Inha University, Incheon 22212, Korea
Jeong Seop Sim: Department of Computer Engineering, Inha University, Incheon 22212, Korea

Mathematics, 2022, vol. 10, issue 12, 1-10

Abstract: Two strings of the same length are order isomorphic if their relative orders are the same. The order-preserving pattern matching problem is to find all substrings of text T that are order isomorphic to pattern P when T ( | T | = n ) and P ( | P | = m ) are given. An O ( m n + n q log q + q ! ) -time algorithm using the O ( m + q ! ) space for the order-preserving pattern matching problem has been proposed utilizing fingerprints of q -grams based on the factorial number system and the bad character heuristic. In this paper, we propose an O ( m n + 2 q ) -time algorithm using the O ( m + 2 q ) space for the order-preserving pattern matching problem, but utilizing fingerprints of q -grams converted to binary numbers. A comparative experiment using three types of time series data demonstrates that the proposed algorithm is faster than existing algorithms because it reduces the number of order isomorphism tests.

Keywords: order isomorphism; order-preserving pattern matching; bad character heuristic; fingerprints (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/12/1954/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/12/1954/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:12:p:1954-:d:833032

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().