📊 statistics

focus and focus-cpt: Fast Online Changepoint Detection in R and Python

This paper introduces the `focus` and `focus-cpt` software packages for R and Python, which implement a family of exact, efficient algorithms for fast online changepoint detection across univariate and multivariate data streams by leveraging the geometric relationship between changepoint candidates and data structure to achieve logarithmic computational complexity without approximations.

Original authors: Gaetano Romano, Kes Ward, Yuntang Fan, Guillem Rigaill, Vincent Runge, Idris A. Eckley, Paul Fearnhead

Published 2026-07-23

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Gaetano Romano, Kes Ward, Yuntang Fan, Guillem Rigaill, Vincent Runge, Idris A. Eckley, Paul Fearnhead

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Science of Spotting the Sudden Shift

Imagine you are watching a river. Most of the time, the water flows at a steady, predictable pace. But suddenly, a massive boulder drops in, or a hidden spring bursts open, and the current changes instantly. In the world of data science, this is called changepoint detection. It is the art of spotting the exact moment a process shifts from one behavior to another. Whether it's a heart monitor detecting an irregular heartbeat, a self-driving car noticing a pedestrian step off the curb, or a satellite sensing a burst of energy from deep space, finding these "boulders" in real-time is crucial.

However, there is a catch. As data streams in—millions of points per second—checking every single possibility for a change becomes a computational nightmare. It's like trying to find a specific grain of sand on a beach by measuring every single grain from the beginning of time every time a new one arrives. This is where online changepoint detection comes in: the challenge of finding the shift as it happens, without getting bogged down by the past. The paper you are about to read tackles this problem with a new, lightning-fast toolkit designed to catch these shifts in data streams, from simple temperature readings to complex, multi-dimensional signals, all while running fast enough for real-time decisions.

The Paper: A Speed Demon for Data Streams

The authors, a team of statisticians and computer scientists, have built a new software package called focus (and its Python twin, focus-cpt) that acts like a super-efficient detective for data streams. Their main finding is that they can calculate the "Generalised Likelihood Ratio" (GLR)—a fancy statistical test that asks, "Did something just change?"—with incredible speed and without cutting any corners.

Usually, checking for a change in a long list of numbers is slow. If you have $n$ data points, a naive method requires checking every possible starting point for a change, which takes a huge amount of computer power (specifically, $O(n^2)$ operations). The authors show that their new method, the focus algorithm, can do this exact same calculation but much faster. Instead of checking every single grain of sand, they use a clever geometric trick. They imagine the data points as a shape (a convex hull) and realize that only the "corners" of this shape matter. By ignoring the points inside the shape, they can prune the list of candidates down to a tiny, manageable size. This means the time it takes to check for a change grows very slowly (logarithmically) even as the data stream gets huge, making it perfect for real-time applications.

What the paper rules out:
The authors explicitly argue against using "approximations" to speed things up. Many other methods try to guess the answer or simplify the math to save time, but the authors insist that their method computes the GLR statistic exactly. They prove that you don't need to sacrifice accuracy for speed; you can have the precise answer without the slow processing time. They also rule out the idea that you must re-scan the entire history of data every time a new point arrives. Their method updates the list of "suspects" (candidate change points) incrementally, discarding those that are no longer relevant.

How sure are they?
The paper presents the method as a mathematical fact: the algorithm computes the exact statistic. However, the performance claims—specifically that it is fast enough for real-time use and works well in complex scenarios—are backed by simulations and demonstrations rather than a single universal proof for every possible real-world scenario. The authors show through various examples (simulated data and real-world case studies) that the method works as advertised. For instance, in their simulations, they show that for a 6-dimensional dataset, their "projection" approximation is significantly faster (taking about 0.166 seconds compared to 10.409 seconds for the full method) while producing results that are nearly identical (a mean relative difference of only 0.0037).

The Toolkit: How It Works in the Wild

The package is available for both R and Python, two popular languages for data science, and they share the same "brain" (a C++ backend), meaning they produce identical results. This makes it easy for scientists to switch between languages without changing their logic.

The toolkit is incredibly flexible. It can handle:

Simple data: Like a single stream of numbers (e.g., temperature).
Complex data: Multiple streams at once (e.g., a sensor on a satellite measuring heat, pressure, and radiation simultaneously).
Different types of data: It works with data that follows specific patterns (like the bell curve of a Gaussian distribution, or the count of events in a Poisson distribution) and even data where you don't know the pattern at all (non-parametric).

The authors demonstrate this flexibility with some cool real-world examples:

NBA Basketball: They analyzed the "Plus-Minus" scores of the Cleveland Cavaliers. By using a custom detector that looked for changes in both the average score and the variability of the scores, they successfully pinpointed the moment the team's performance shifted, which coincided with the return of a famous player.
Gamma-Ray Bursts: In the vastness of space, gamma-ray bursts are intense flashes of energy that last only a fraction of a second. The authors used their Python tool to detect these bursts in real-time from satellite data. Because the tool is so fast, it can identify the most significant moment of the burst as it happens, without needing to know beforehand how long the burst will last.
Brain Spikes: They applied the tool to calcium imaging data, which measures the electrical activity of neurons. By using two detectors—one watching for spikes up and one for drops down—they could infer when neurons fired in real-time, a crucial step for "closed-loop" experiments where a computer reacts to brain activity instantly.

The "Magic" Behind the Speed

To understand why this is a big deal, imagine you are a security guard watching a video feed of a crowded street. A naive system would stop the video, rewind to the start, and check every single frame to see if a person changed their clothes. This would take forever. The focus algorithm is like a guard who only remembers the "corners" of the crowd's movement. If a person walks in a straight line, the guard ignores them. But the moment someone makes a sharp turn (a change), the guard instantly flags it.

The paper explains that this "corner" logic comes from the geometry of the data. By converting the data into a specific shape, the algorithm can mathematically prove that any point inside the shape is impossible to be the start of a change. This allows the computer to "prune" (cut out) thousands of unnecessary checks instantly.

For high-dimensional data (where you have many sensors), the authors introduce a smart shortcut. Instead of trying to find the corners of a complex, multi-dimensional shape (which is hard), they project the data onto smaller, overlapping 2D or 3D slices, find the corners there, and combine the results. They show in their simulations that this "projection" method is vastly faster than trying to calculate the full shape, yet it catches the changes just as well.

Why It Matters

The ultimate goal of this paper is to provide a common, fast, and accurate interface for scientists and engineers who need to detect changes in data streams right now. Whether it's monitoring the health of a power grid, spotting a cyberattack, or decoding a neuron's signal, the ability to process data exactly and efficiently in real-time is a game-changer. The authors have successfully bridged the gap between complex statistical theory and practical, usable software, proving that you don't have to choose between being fast and being right. You can have both.

Technical Summary: focus and focus-cpt

Problem Statement

The paper addresses the challenge of fast online changepoint detection in univariate and multivariate data streams. While offline changepoint detection has seen significant methodological advances, real-world applications in engineering, cybersecurity, neuroscience, and astrophysics increasingly require real-time analysis of high-frequency data.

The core statistical problem involves testing whether the underlying distribution of a data stream has changed at an unknown location. The standard approach utilizes the Generalised Likelihood Ratio (GLR) test, which compares the likelihood of the data under a null hypothesis (no change) against an alternative hypothesis (a change occurred at some unknown time $\tau$ ). However, a naive sequential implementation of the GLR test requires $O(n)$ operations per time step to evaluate all $n-1$ candidate changepoint locations, resulting in an overall $O(n^2)$ complexity. This computational burden renders exact GLR testing infeasible for true real-time applications involving long data streams.

Methodology

The paper presents the focus family of algorithms, implemented in the focus (R) and focus-cpt (Python) packages. These algorithms compute the GLR statistic exactly (without approximation) but achieve a per-iteration cost of approximately $O(\log(n)^d)$ for a $d$ -dimensional sequence.

Core Algorithmic Insight

The efficiency of the focus algorithm relies on a geometric insight connecting the location of changepoint candidates to the geometry of the data's random walk.

Pruning via Convex Hulls: The algorithm identifies that only a subset of candidate changepoints $\tau$ can ever be the maximizer of the GLR statistic for any pair of pre- and post-change parameters $(\theta_0, \theta_1)$ .
Geometric Representation: By defining a data-dependent vector $P(\tau) = (\tau, \sum_{t=1}^\tau T(y_t))$ and a model-dependent vector $\psi(\theta_0, \theta_1)$ , the log-likelihood ratio becomes a scalar product $\langle P(\tau), \psi(\theta_0, \theta_1) \rangle$ .
Active Set Maintenance: Maximizing this scalar product is equivalent to finding the vertex of the convex hull of the set $\{P(\tau)\}$ that is furthest in the direction of $\psi$ . Consequently, any candidate $\tau$ whose $P(\tau)$ lies in the interior of the convex hull can be permanently pruned.
Computational Complexity:
- Univariate: The algorithm maintains the hull vertices using a method related to the Melkman algorithm, achieving an amortized $O(1)$ cost per iteration.
- Multivariate: For $d$ -dimensional data, the expected size of the active candidate set grows as $O(\log(n)^d)$ . The implementation uses the QuickHull algorithm intermittently to maintain the hull. For high dimensions, an approximation projects data onto overlapping subsets of $\tilde{d} \leq 5$ coordinates to reduce computational burden while retaining statistical performance.

Supported Models

The package supports a broad range of models from the natural exponential family and other specific structures:

Parametric Models: Gaussian (change in mean or variance), Poisson, Binomial, Exponential, and Gamma distributions.
Non-Parametric: A detector based on the empirical cumulative distribution function (eCDF), which transforms the problem into multiple Binomial detection problems across quantiles.
Autoregressive (AR): A detector for AR( $p$ ) processes that accounts for temporal dependencies and transient behavior immediately following a changepoint, avoiding the pitfalls of simple pre-whitening.

Software Implementation

The package provides unified interfaces in R (focus) and Python (focus-cpt), sharing a common C++ backend. This ensures functional parity and identical results across both languages. The interface supports:

Online (Sequential) Mode: Updates the detector state incrementally as data arrives.
Offline (Batch) Mode: Processes entire datasets for retrospective analysis or threshold calibration.
Modularity: Separation of the detector state (pruning logic) from cost functions (statistic evaluation), allowing users to implement custom cost functions without re-implementing the core pruning algorithm.

Key Contributions

Exact GLR with Logarithmic Complexity: The primary contribution is an algorithm that computes the exact GLR statistic with a computational cost that grows logarithmically with the sequence length, making it suitable for real-time applications where naive $O(n^2)$ approaches fail.
Unified Framework: A single software package supporting a wide variety of distributions (Gaussian, Poisson, etc.), dimensions (univariate to multivariate), and data structures (i.i.d., non-parametric, autoregressive).
Geometric Pruning: A rigorous demonstration of how convex hull geometry can be exploited to prune the search space of changepoint candidates without sacrificing statistical optimality.
Accessibility: Providing robust, production-ready implementations in both R and Python, facilitating adoption by practitioners in diverse fields.

Results and Applications

The paper validates the methodology through simulated examples and real-world applications:

Simulation: Demonstrates the algorithm's ability to detect changes in means, variances, and non-parametric distribution shifts. It highlights the efficiency of the projection-based approximation for high-dimensional data, showing significant speedups with negligible loss in statistical accuracy.
NBA Plus-Minus Scores: Applied to Cleveland Cavaliers game data to detect changes in team performance (mean and variance) over seasons. The custom cost function successfully identified the 2014-2015 season change corresponding to LeBron James's return, demonstrating robustness against variance shifts.
Gamma-Ray Burst (GRB) Detection: Used on Fermi-GBM data to detect GRB250814432. The focus-based trigger identified the most significant interval of the burst in real-time without prior knowledge of the burst duration, outperforming traditional thresholding methods in terms of identifying the optimal detection window.
Spike Inference: Applied to calcium imaging data to infer neuronal spike times in real-time. By using two coupled one-sided detectors (for up-changes and decay), the method achieved low-latency processing suitable for closed-loop experiments.

Significance

The paper positions the focus package as a critical tool for bridging the gap between rigorous statistical theory and the practical demands of real-time data analysis. By solving the computational bottleneck of exact GLR testing, it enables the deployment of statistically optimal changepoint detection in scenarios previously limited to approximate or slower methods. The authors emphasize that the software is designed to be a common interface for the focus family of algorithms, supporting diverse use cases from IoT monitoring to astrophysics, and facilitating the transition from offline retrospective analysis to online, decision-making systems. The work builds upon and extends previous methodological developments (Romano et al. 2023b; Ward et al. 2024; Pishchagina et al. 2025) into a unified, accessible software ecosystem.