Search

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. [ABSTRACT FROM AUTHOR]