@article{M2118D1FB,
title = "Parallel Computation of Order-Preserving Periods and Order-Preserving Borders of a Set of Strings",
journal = "Journal of KIISE, JOK",
year = "2019",
issn = "2383-630X",
doi = "10.5626/JOK.2019.46.12.1232",
author = "Youngho Kim,Jeong Seop Sim",
keywords = "GPU,order-preserving pattern matching,order-preserving periods,order-preserving borders,parallel algorithm",
abstract = "Given two strings of the same length over an integer alphabet, those two strings are order-isomorphic when they have the same relative ranks. When strings order-isomorphic to T[1..p](1 ≤ p ≤ n) are periodically repeated in T, a representation of the order relations of T[1..p] is referred to as an order-preserving period of T. When a prefix T[1..q] (1 ≤ q ≤ n) of T is order-isomorphic to a suffix T[n-q+1..n] of T, a representation of the order relations of T[1..q] is called an order-preserving border of T. The lengths of all order-preserving periods (resp. all order-preserving borders) of T can be computed in O(n logn) time using the Z-function. Given a set Ŝ=｛S₁, S₂,..., S<SUB>r</SUB>｝of strings of length n over an integer alphabet, we propose parallel algorithms computing the lengths of all order-preserving periods and all order-preserving borders of Ŝ using O(rn) threads in O(n) time by the Z-function. When compared to each sequential algorithm for Dow Jones Industrial Average, the experimental results show that our parallel algorithm for computing the lengths of all order-preserving periods (resp. all order-preserving borders) of Ŝ runs approximately 3.47 (resp. 3.41) times faster when r =1,000, n =10,000."
}