TY  - JOUR
T1  - An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams
AU  - Yoo, Gwangmo 
AU  - Kim, Youngho 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2018
DA  - 2018/1/14
DO  - 10.5626/JOK.2018.45.11.1111
KW  - order-isomorphism
KW  - order-preserving pattern matching
KW  - q-gram
KW  - fingerprint
AB  - Given a text T of length n and a pattern P of length m, the order-preserving pattern matching problem is to find all substrings in T that have the same relative orders as P. Recently, an O(nm+nqlogq+q!)-time order-preserving pattern matching algorithm was proposed that uses fingerprints of q-grams. In this paper, we propose an order-preserving pattern matching algorithm using the fingerprints of two q-grams to improve execution times. The experimental results for randomly generated T (n = 5,000,000) and P (m = 5,10,15) show that our algorithm runs up to approximately 12% faster than the previous algorithm. Also, for T using Dow Jones Industrial Average (n = 34,658) and P (m = 5,10,15) randomly extracted from T, our algorithm runs up to approximately 10% faster than the previous algorithm.