Identifying periodic patterns in time series data is crucial for uncovering hidden structures and predicting future events. Recognizing meaningful periodic patterns in real data requires handling approximation criteria since periodic phenomena are usually inexact. This paper introduces a suitable criterion and focuses on detecting Consecutive Periodic Patterns (CPPs) with$k \Delta$-errors, where$k$bounds the number of errors and$\Delta$limits the size of the error. We develop efficient algorithms to detect the Longest Pure Consecutive Maximal Periodic Pattern with bounded errors in both raw and compressed data, the latter by means of the Arithmetic Progressions Tree (APT) data structure.

The Arithmetic Progressions Tree (APT) is a data structure storing an encoding of a monotonic sequence$\mathcal{L}$in$[1..n]$. While previous work on$\mathsf{APT}$focused on its theoretical and experimental compression guarantees, recently, it was shown that searches of sub-sequences, runs and periodic patterns over the$\mathsf{APT}$compressed data can be applied. This paper extends the set of supported operations and focuses on the computation of consecutively maximal periodic patterns directly over the APT. In particular, given the$\mathsf{APT}$compressed representation of$\mathcal{L}$, we show how: (1)One can find if a consecutive periodic pattern with difference$d_{P}$is represented by an$\mathsf{APT}$node in time$O(\log n)$and if positive, report its occurrences in$\mathcal{L}$in time proportional to the output size multiplied by$\log d_{P}$and the size of the$\mathsf{APT}$compressed representation of$\mathcal{L}$, while assuring that every reported consecutive occurrence is consecutively maximal. (2)Given a query periodic pattern difference,$d_{P}$, we can give a one-sided$O(\log d_{P})$-additive approximation for the length of the consecutively maximal periodic pattern with difference$d_{P}$that occurs in$\mathcal{L}$in time$O(\log n)$. (3)We give a one-sided$O(\log n)$-additive approximation for the maximum length of a consecutively maximal periodic pattern that occurs in$\mathcal{L}$in time$O(\sqrt{n}\log n)$.

The Arithmetic Progressions Tree (APT) is an encoding of a monotonic sequence ℒ in [1..n]. Previous work on APT coding focused on its theoretical and experimental compression guarantees. This paper is the first to consider computations over APT compressed data. In particular: (1) We show how to perform a search for any sub-sequence of the monotone sequence ℒ in time proportional to the query sub-sequence length multiplied by the size of the APT compressed representation of ℒ. (2) We show how, given the APT compressed representation of the monotone sequence ℒ, we can find a minimum run-length of ℒ in constant time, a maximum run-length of ℒ in O(log n) time, and all runs of ℒ in constant time plus the output size. (3) Most importantly, we show how, given the APT compressed representation of the monotone sequence ℒ, we can answer whether a periodic pattern P appears in ℒ in O(log n) time and report its locations in the output size time. (4) In addition, we improve the APT construction algorithm time and space complexity.