# A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 6 Feb 2023.

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

- [A Nonparametric Approach for Multiple Change Point Analysis of Multivariate Data](https://mlsanity.com/paper/1306.4933/) (2013)
- [High-dimensional, multiscale online changepoint detection](https://mlsanity.com/paper/2003.03668/) (2020)
- [NEWMA: a new method for scalable model-free online change-point detection](https://mlsanity.com/paper/1805.08061/) (2018)
- [Change Detection with the Kernel Cumulative Sum Algorithm](https://mlsanity.com/paper/1903.01661/) (2019)
- [Sequential change-point detection based on nearest neighbors](https://mlsanity.com/paper/1604.03611/) (2016)
- [Seeded Binary Segmentation: A general methodology for fast and optimal change point detection](https://mlsanity.com/paper/2002.06633/) (2020)
- [Real-Time Nonparametric Anomaly Detection in High-Dimensional Settings](https://mlsanity.com/paper/1809.05250/) (2018)
- [Fast Online Changepoint Detection via Functional Pruning CUSUM statistics](https://mlsanity.com/paper/2110.08205/) (2021)
- [Online Kernel CUSUM for Change-Point Detection](https://mlsanity.com/paper/2211.15070/) (2022)
- [Window-Limited CUSUM for Sequential Change Detection](https://mlsanity.com/paper/2206.06777/) (2022)
- [Fast Nonconvex Deconvolution of Calcium Imaging Data](https://mlsanity.com/paper/1802.07380/) (2018)
- [Detecting Abrupt Changes in the Presence of Local Fluctuations and Autocorrelated Noise](https://mlsanity.com/paper/2005.01379/) (2020)
- [Sequential Change-point Detection for High-dimensional and non-Euclidean Data](https://mlsanity.com/paper/1810.05973/) (2018)
- [Changepoint detection in non-exchangeable data](https://mlsanity.com/paper/2111.05054/) (2021)
- [Data segmentation algorithms: Univariate mean change and beyond](https://mlsanity.com/paper/2012.12814/) (2020)
- [Nonparametric Detection of Multiple Location-Scale Change Points via Wild Binary Segmentation](https://mlsanity.com/paper/2107.01742/) (2021)
- [Detecting A Single Change-point](https://mlsanity.com/paper/2210.07066/) (2022)

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

- [A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint Detection for Exponential Family Models](https://mlsanity.com/paper/2302.04743/) (2023)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)
- [Conformal Changepoint Localization and Root Cause Analysis with Corrupted Observations](https://mlsanity.com/paper/2607.26481/) (2026)
- [Predictive maintenance solution for industrial systems -- an unsupervised approach based on log periodic power law](https://mlsanity.com/paper/2408.05231/) (2024)
- [Accurate Evaluation of Quickest Changepoint Detectors via Non-parametric Survival Analysis](https://mlsanity.com/paper/2605.18798/) (2026)
- [An Efficient Likelihood Ratio Test for Online Changepoint Detection in the Presence of Autocorrelation](https://mlsanity.com/paper/2607.16106/) (2026)
- [One Residual with Three Reuses: A Wristband Front End for Gesture Sensing](https://mlsanity.com/paper/2608.16542/) (2026)

## Abstract (arXiv)

Online changepoint detection aims to detect anomalies and changes in real-time in high-frequency data streams, sometimes with limited available computational resources. This is an important task that is rooted in many real-world applications, including and not limited to cybersecurity, medicine and astrophysics. While fast and efficient online algorithms have been recently introduced, these rely on parametric assumptions which are often violated in practical applications. Motivated by data streams from the telecommunications sector, we build a flexible nonparametric approach to detect a change in the distribution of a sequence. Our procedure, NP-FOCuS, builds a sequential likelihood ratio test for a change in a set of points of the empirical cumulative density function of our data. This is achieved by keeping track of the number of observations above or below those points. Thanks to functional pruning ideas, NP-FOCuS has a computational cost that is log-linear in the number of observations and is suitable for high-frequency data streams. In terms of detection power, NP-FOCuS is seen to outperform current nonparametric online changepoint techniques in a variety of settings. We demonstrate the utility of the procedure on both simulated and real data.