Detecting approximate periodic patterns

Given ϵ ∈ [ 0, 1 ), the ϵ-Relative Error Periodic Pattern Problem (REPP) is the following: INPUT: An n-long sequence S of numbers s i ∈ N in increasing order. OUTPUT: The longest ϵ-relative error periodic pattern, i. e. , the longest subsequence s i 1, s i 2, …, s i k of S, for which there exists a number p such that the absolute difference between any two consecutive numbers in the subsequence is at least p and at most p ( 1 + ϵ ). The best known algorithm for this problem has O ( n 3 ) time complexity. This bound is too high for large inputs in practice. In this paper we give a new algorithm for finding the longest ϵ-relative error periodic pattern (the REPP problem). Our method is based on a transformation of the input sequence into a different representation: the ϵ-active maximal intervals list L, defined in this paper. We show that the transformation of S to the list L can be done efficiently (quadratic in n and linear in the size of L) and prove that our algorithm is linear in the size of L. This enables us to prove that our algorithm works in sub-cubic time on inputs for which the best known algorithm works in O ( n 3 ) time. Moreover, though it may happen that our algorithm would still be cubic, it is never worse than the known O ( n 3 ) -algorithm and in many situations its complexity is O ( n 2 ) time.

Authors

• Amihood Amir
• Alberto Apostolico
• Estrella Eisenberg
• Gad M. Landau
• Avivit Levy
• Noa Lewenstein

Keywords

• String analysis
• Approximate periodic patterns
• Approximate arithmetic progressions