Detecting approximate periodic patterns

Autor: Amihood Amir, Avivit Levy, Gad M. Landau, Estrella Eisenberg, Alberto Apostolico, Noa Lewenstein
Rok vydání: 2014
Předmět:
Zdroj: Theoretical computer science (Berl. West) 525 (2014): 60–67.
info:cnr-pdr/source/autori:Amihood Amir, Alberto Apostolico, Estrella Eisenberg, Gad M. Landau, Avivit Levy, Noa Lewenstein/titolo:Detecting approximate periodic patterns/doi:/rivista:Theoretical computer science (Berl. West)/anno:2014/pagina_da:60/pagina_a:67/intervallo_pagine:60–67/volume:525
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2013.05.001
Popis: Given @e@?[0,1), the @e-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 @e-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+@e). 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 @e-relative error periodic pattern (the REPP problem). Our method is based on a transformation of the input sequence into a different representation: the @e-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.
Databáze: OpenAIRE
Externí odkaz: