Order-preserving pattern matching indeterminate strings

Given a pattern p of size m and a text t, the problem of order-preserving pattern matching (OPPM) is to find all substrings of t that satisfy one of the orderings defined by p. This problem has applications on time series analysis. However given its strict nature this model is unable to deal with indetermination, thus limiting its application to noisy time series. In this paper we introduce indeterminate characters to alleviate this limitation. We then propose two polynomial time algorithms. If the indetermination is limited to p confirming one occurrence can be computed in O ( r m lg ⁡ r ) time, where r is a bound on the number of uncertain characters per position. If the indetermination alternates, but does not occur at the same position in t and p, we present an algorithm that requires O ( r m ( m + log ⁡ r ) ) time. We also show that the general problem is NP-hard and provide a polynomial size boolean formula.

Authors

• Luís M.S. Russo
• Diogo Costa
• Rui Henriques
• Hideo Bannai
• Alexandre P. Francisco

Keywords

• Order-preserving pattern matching
• Indeterminate string analysis
• Generic pattern matching
• Satisfiability