Classifying Pattern and Feature Properties to Get a $Θ(n)$ Checker and Reformulation for Sliding Time-Series Constraints
This work addresses computational efficiency in constraint programming for time-series analysis, though it appears incremental as it builds on existing sliding constraint methods.
The paper tackles the problem of efficiently checking and reformulating sliding time-series constraints by developing a checker with Θ(n) time complexity and a reformulation with Θ(n) space complexity, achieving linear scaling for sequences of n variables.
Given, a sequence $\mathcal{X}$ of $n$ variables, a time-series constraint ctr using the Sum aggregator, and a sliding time-series constraint enforcing the constraint ctr on each sliding window of $\mathcal{X}$ of $m$ consecutive variables, we describe a $Θ(n)$ time complexity checker, as well as a $Θ(n)$ space complexity reformulation for such sliding constraint.