# Geometric-Based Pruning Rules For Change Point Detection in Multiple Independent Time Series

arXiv: https://arxiv.org/abs/2306.09555 · HTML: https://mlsanity.com/paper/2306.09555/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 47 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 8 of 8)

- [Testing for a Change in Mean After Changepoint Detection](https://mlsanity.com/paper/1910.04291/) (2019)
- [On Optimal Multiple Changepoint Algorithms for Large Data](https://mlsanity.com/paper/1409.1842/) (2014)
- [Multiscale Change-Point Inference](https://mlsanity.com/paper/1301.7212/) (2013)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Detecting changes in slope with an L0 penalty](https://mlsanity.com/paper/1701.01672/) (2017)
- [Increased peak detection accuracy in over-dispersed ChIP-seq data with supervised segmentation models](https://mlsanity.com/paper/2012.06848/) (2020)
- [Detecting multiple generalized change-points by isolating single ones](https://mlsanity.com/paper/1901.10852/) (2019)
- [Is a Finite Intersection of Balls Covered by a Finite Union of Balls in Euclidean Spaces ?](https://mlsanity.com/paper/1804.06699/) (2018)

## Abstract (arXiv)

We consider the problem of detecting multiple changes in multiple independent time series. The search for the best segmentation can be expressed as a minimization problem over a given cost function. We focus on dynamic programming algorithms that solve this problem exactly. When the number of changes is proportional to data length, an inequality-based pruning rule encoded in the PELT algorithm leads to a linear time complexity. Another type of pruning, called functional pruning, gives a close-to-linear time complexity whatever the number of changes, but only for the analysis of univariate time series. We propose a few extensions of functional pruning for multiple independent time series based on the use of simple geometric shapes (balls and hyperrectangles). We focus on the Gaussian case, but some of our rules can be easily extended to the exponential family. In a simulation study we compare the computational efficiency of different geometric-based pruning rules. We show that for small dimensions (2, 3, 4) some of them ran significantly faster than inequality-based approaches in particular when the underlying number of changes is small compared to the data length.