changepoint-edivisive

E-Divisive change point detection with Hunter's t-test refinement, in Rust, with a WASM build for Node and the browser.

Given a noisy time series it tells you where the distribution changed — which build made things slower, which deploy shifted a latency curve — without assuming a distribution, a number of change points, or a threshold to compare against.

use changepoint_edivisive::{detect, Options};

let cps = detect(&latencies_ms, &Options::default());
for cp in &cps {
    println!(
        "index {}: {:.1} -> {:.1} ms ({:+.1}%), p = {:.2e}",
        cp.index,
        cp.mean_before,
        cp.mean_after,
        cp.forward_rel_change() * 100.0,
        cp.pvalue,
    );
}

import { createRequire } from "node:module";
const { detectChangePoints } = createRequire(import.meta.url)("changepoint-edivisive");

const cps = JSON.parse(detectChangePoints(Float64Array.from(latenciesMs)));

Why this exists

The algorithm comes from two papers — E-Divisive (Matteson & James) for finding the points, and Hunter (Fleming et al.) for making it practical on benchmark data. The only maintained implementation was inside Apache Otava, in Python. This is a port of Otava's detector so the same analysis can run in Rust, in a Node service, or in a browser.

Correctness is defined by agreement with Otava: fixtures/ holds 31 series with the change points the real Otava detector reports for them, and tests/parity.rs requires index-for-index agreement on every one. tests/wasm.test.mjs replays the same fixtures through the compiled WASM artifact.

There are no runtime dependencies. The only special function needed is a regularized incomplete beta (for the t distribution), and the crates that provide it pull in nalgebra and getrandom, which do not build for wasm32-unknown-unknown without a shim. The WASM binary is ~76 KB.

How it works

1. Split. Slide a window over the series. In each window, recursively bisect at the point maximizing the E-Divisive divergence statistic Q, keeping splits that pass a relaxed significance threshold. Union the results.
2. Merge. Walk the candidates bottom-up, repeatedly discarding the weakest, until every survivor clears both max_pvalue and min_magnitude. Removing a point widens its neighbours' segments, so their statistics get restated.

Hunter's contribution is replacing E-Divisive's permutation test with a two-sided Student's t-test — faster, deterministic, and better behaved on the small samples typical of benchmark history.

Options

| Option | Default | Meaning | |---|---|---| | window_len | 50 | Sliding window length for the split step. Must be >= 2. | | max_pvalue | 0.001 | Significance a change point must reach to survive. | | min_magnitude | 0.0 | Minimum relative change, e.g. 0.05 to ignore anything under 5%. |

A series shorter than 3 points can never yield a change point: two points are either equal or different, with no context for judging whether the difference means anything.

Development

cargo test                                              # unit + parity fixtures
cargo clippy --all-targets

wasm-pack build --target nodejs --out-dir pkg -- --features wasm
node --test tests/wasm.test.mjs

Regenerating the golden fixtures needs an environment with apache-otava installed; the fixtures are checked in so ordinary builds and CI never need it.

# any python that can `import otava` — e.g. an otava checkout's venv
/path/to/otava/.venv/bin/python scripts/gen-fixtures.py
/path/to/otava/.venv/bin/python scripts/gen-fixtures.py --check   # fail if stale

License

Apache-2.0. See NOTICE for attribution — this is a reimplementation of Apache Otava's detector, and the algorithm is from the papers above.