# Seeded Binary Segmentation: A general methodology for fast and optimal change point detection

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Feb 2020.

## Built on by (most cited first, 11 of 11)

- [Random Forests for Change Point Detection](https://mlsanity.com/paper/2205.04997/) (2022)
- [A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning](https://mlsanity.com/paper/2302.02718/) (2023)
- [Segmenting Watermarked Texts From Language Models](https://mlsanity.com/paper/2410.20670/) (2024)
- [Causal Discovery-Driven Change Point Detection in Time Series](https://mlsanity.com/paper/2407.07290/) (2024)
- [Finite Sample Complexity Analysis of Binary Segmentation](https://mlsanity.com/paper/2410.08654/) (2024)
- [Vulnerability Disclosure through Adaptive Black-Box Adversarial Attacks on NIDS](https://mlsanity.com/paper/2506.20576/) (2025)
- [Adaptive Testing for Segmenting Watermarked Texts From Language Models](https://mlsanity.com/paper/2511.06645/) (2025)
- [The Sample Complexity of Multiple Change Point Identification under Bandit Feedback](https://mlsanity.com/paper/2605.13252/) (2026)
- [High-dimensional nonparametric changepoint detection via low-rank degree-two density projection](https://mlsanity.com/paper/2608.13922/) (2026)
- [High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection](https://mlsanity.com/paper/2608.15466/) (2026)
- [skchange: Fast and Flexible Algorithms for Changepoint Detection](https://mlsanity.com/paper/2608.19767/) (2026)

## Abstract (arXiv)

In recent years, there has been an increasing demand on efficient algorithms for large scale change point detection problems. To this end, we propose seeded binary segmentation, an approach relying on a deterministic construction of background intervals, called seeded intervals, in which single change points are searched. The final selection of change points based on the candidates from seeded intervals can be done in various ways, adapted to the problem at hand. Thus, seeded binary segmentation is easy to adapt to a wide range of change point detection problems, let that be univariate, multivariate or even high-dimensional. We consider the univariate Gaussian change in mean setup in detail. For this specific case we show that seeded binary segmentation leads to a near-linear time approach (i.e. linear up to a logarithmic factor) independent of the underlying number of change points. Furthermore, using appropriate selection methods, the methodology is shown to be asymptotically minimax optimal. While computationally more efficient, the finite sample estimation performance remains competitive compared to state of the art procedures. Moreover, we illustrate the methodology for high-dimensional settings with an inverse covariance change point detection problem where our proposal leads to massive computational gains while still exhibiting good statistical performance.