Computing Consecutively Maximal Periodic Patterns Over APT Compressed Data

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)$.