@article{M8E7BEE28,
title = "An Order-Preserving Pattern Matching Algorithm using Fingerprints of Two q-grams",
journal = "Journal of KIISE, JOK",
year = "2018",
issn = "2383-630X",
doi = "10.5626/JOK.2018.45.11.1111",
author = "Gwangmo Yoo,Youngho Kim,Jeong Seop Sim",
keywords = "order-isomorphism,order-preserving pattern matching,q-gram,fingerprint",
abstract = "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."
}