Cheap, Scalable Time-Series Anomaly Detection — 10M–150M Series, Online Training, Daily Batch OK

0. TL;DR

1. 150M series is feasible — it is a solved problem at the storage/platform layer, and the cheap algorithms scale too. VictoriaMetrics single-node is documented for up to 100M active series and the cluster version for billions (VM FAQ). Anodot ran anomaly detection over >120M series, >6B data points/day in production in 2017 (Anodot, PMLR 71). So the target is within demonstrated practice — not a "downgrade to 10M" situation. 10M is trivially within range.
2. The binding constraint is per-series model state and per-point compute, not raw storage. Keep per-series state in the hundreds of bytes to a few KB range (bounded sufficient statistics, seasonal coefficients, an anomaly threshold), and every series is cheap. This is exactly what the streaming/statistical methods do. Per-series deep networks or big forests break the budget at 150M.
3. The cheap tier that dominates = "residual + adaptive threshold": model the expected value (EWMA / Holt-Winters / z-score / median-seasonal), flag points whose residual exceeds an adaptively learned threshold (Extreme-Value-Theory SPOT/POT, or online MAD/quantile/z-score). O(1) per point, tiny state, online by construction, no GPU.
4. Online training is the default for these methods — it's an O(1) state update, not SGD. EWMA/CUSUM, Bayesian Online Changepoint Detection, SPOT/DSPOT, Random Cut Forest (streaming insert), and Holt-Winters recursive updates all update incrementally as points arrive. "Online" at 150M series must mean closed-form per-point state updates, not gradient descent per series.
5. Daily batch is fully supported and is a valid operating point. VictoriaMetrics vmanomaly and Merlion/Greykite all let you schedule fit_every: 1d (batch refit) or run truly online models with exponential decay. You can mix: a cheap online scorer every point + a heavier model refit daily on a filtered subset.
6. Recommended shape: a two-tier pipeline — (Tier 1) a cheap streaming statistical detector on every series/every point, (Tier 2) a heavier model (RRCF or shared/global model) escalated only on flagged windows. This is the same split Uber uses in production (outlier detector → outage detector) and is how you keep 150M-series cost bounded.

1. Constraints restated

• 150M unique series (10M fallback). Any per-series cost — parameters, state, compute, storage — is multiplied by ~1.5×10⁸.
• Cheap — CPU-only, low per-point cost, low memory, low ops overhead (no hand-tuning 150M models).
• Online training supported — the model must be able to learn/adapt incrementally as new data arrives.
• Batch (daily) acceptable but not strict — a daily refit/run cadence is fine; continuous streaming is a bonus, not a hard requirement.
• Highly extensible — pluggable model families, easy to add series and swap algorithms without re-architecting.

2. Feasibility verdict (the "150M vs 10M" question)

Storage/platform layer — 150M is proven. - VictoriaMetrics: single-node handles up to 100M active time series and 2M samples/s; the cluster version handles billions of active series and hundreds of millions of samples/s (based on real usage). — VictoriaMetrics FAQ, "scalability limits" - Anodot's commercial system (peer-reviewed description): "discovers anomalies today for about 50 different companies and over 120 million time series metrics", processing "over 6 billion data points per day", with ~20M of those series found to have seasonal patterns. — Toledano et al., PMLR 71:56–65, 2018 - Uber's Argos monitors "tens of millions of metrics" in real time. — Uber Engineering, "Identifying Outages with Argos"

Model layer — this is where the 150M vs 10M distinction actually lives.

• 10M series: you can afford ~1–100 KB of state per series (even a modest per-series forest or small adapter) within a few TB. Almost any "cheap" method fits.
• 150M series: you are essentially restricted to O(1)-state statistical methods (EWMA/CUSUM, online mean/variance, seasonal coefficients, a single EVT/quantile threshold) unless you spill state to disk. VictoriaMetrics vmanomaly supports an on-disk model mode for exactly this reason: "dumped to disk … significantly decreases RAM usage, particularly useful for larger setups" (vmanomaly models doc).

Conclusion: 150M is achievable, but only if per-series state is bounded to statistical summaries. The methods below are ordered by that budget.

3. The "cheap" method hierarchy (what to pick, and why)

3.1 Statistical streaming detectors — O(1) state, O(1)/point, online by construction

These are the cheapest and the ones that actually scale to 150M.

• EWMA / CUSUM / control charts. Classical statistical process control; maintain a running level (and optionally variance), flag points when the deviation exceeds a control limit. Closed-form, incremental, no history retained. (Background: the same exponential-weighting idea is the default "exp_avg_detector" in LinkedIn's Luminol, with a smoothing factor controlling adaptation — Luminol README.)
• Online z-score / MAD / quantile. Running mean+std (or median+MAD for robustness) with a fixed multiple-of-sigma threshold. These are built-in first-class "online" models in VictoriaMetrics vmanomaly (zscore_online, quantile_online, online MAD), and vmanomaly's docs explicitly recommend them as the cheap default for stationary/light-tailed data. — vmanomaly models doc
• Seasonality via online/forecast residual. Holt-Winters (triple exponential smoothing) / ETS forecast the expected value including daily/weekly seasonality; the anomaly score is the forecast residual. This is the core of:
• Yahoo EGADS — splits the problem into a Time-Series Model (forecaster: OlympicModel, TripleExponentialSmoothingModel, etc.) + an Anomaly Detection Model (KSigma, density-based, SimpleThresholdModel with adaptive sensitivity). EGADS's own README: "At Yahoo, our internal Yahoo Monitoring Service (YMS) processes millions of data-points every second." — EGADS README
• Anodot — per-series model chosen by a classifier (~40% of metrics are stationary; the rest sparse/step/discrete/multi-modal/irregular), parameters fit by MLE, then an online adaptive policy updates the model as points arrive. — Anodot, PMLR 71
• Greykite (LinkedIn) — forecast with Silverkite, flag points outside the forecast confidence interval; "Simple Anomaly Detection" auto-tunes the interval (by expected alert rate / APE) instead of hand-setting it. — Greykite simple AD docs

3.2 Adaptive thresholds (no manual threshold, no distribution assumption)

• SPOT / POT (Extreme Value Theory). SPOT adapts Peaks-Over-Threshold to streams: it fits a Generalized Pareto Distribution to the tail of the residual stream and computes a high quantile as the anomaly threshold, with no manual threshold and no distributional assumption, updating as data flows. The reference implementation, libspot, is a C99, -nostdlib library for "high-throughput streaming data," self-described as "the poor man's anomaly detector" and "a cheap algorithm that must be able to run on cheap systems." — libspot · SPOT, KDD 2017
• Bayesian Online Changepoint Detection (Adams & MacKay). Derives an exact online inference of the most recent changepoint / run-length via a simple message-passing algorithm — a principled, fully-online alternative to fixed thresholds that detects both point anomalies and regime shifts. — arXiv:0710.3742

3.3 Robust Random Cut Forest (RRCF) — streaming, but a "heavier" second stage

• RRCF is an unsupervised streaming detector: each tree scores a point by the expected change in tree complexity when inserted, and the model is updated incrementally (reservoir sampling, so it works on unbounded streams). "Inference time is proportional to the number of trees"; the docs recommend 100 trees to start. — Amazon SageMaker, "How RCF works" · Guha et al., ICML 2016
• Cost note: RRCF's per-series state is num_trees × num_samples_per_tree points — in Merlion's default config that's n_estimators=100, max_n_samples=512 ≈ 51k points/series, i.e., ~hundreds of KB per series, not bytes. At 150M series that is ~60 TB (see §2). So use RRCF as the escalated second stage on flagged windows, or with a very small sample size, not as the always-on 150M-series scorer. (Merlion's own default detector uses exactly this pattern — see §4.1.)

3.4 Subsequence/motif methods — note but don't default to them

• Matrix Profile / STUMPY finds discords (unusual subsequences) rather than point outliers. It is excellent for shape-based anomalies but is quadratic (or O(n log n) with SCRIMP-type approximations) per series and not "cheap" at 150M. Mentioned for completeness; not recommended as the 150M-series default. — UCR Matrix Profile page · STUMPY

4. Turnkey / semi-turnkey options (primary sources)

4.1 VictoriaMetrics vmanomaly (built for high-cardinality metrics)

• Built on VictoriaMetrics, which scales to 100M (single-node) / billions (cluster) series — the anomaly service is designed for exactly this cardinality regime. — VM FAQ
• Online models: zscore_online, quantile_online (online seasonal quantile), online MAD, and temporal_envelope (trend + calendar/holiday + seasonal patterns; the recommended online replacement for Prophet). — vmanomaly models
• Online adaptation knob: the decay parameter gives an exponential forgetting factor to online models so they "adapt to new data" without full refits (e.g., decay: 0.996 keeps ~1 day of data dominant at 1-min granularity). — vmanomaly models → Decay
• Batch/daily and hybrid scheduling: the scheduler defines fit_every / fit_window / infer_every. You can run offline models on a daily refit (fit_every: 1d) or online models with a bootstrap-only fit (fit_every: 1000d + infer_every: 5m) — i.e., daily batch and streaming are both first-class. — vmanomaly FAQ / scheduler
• All models emit a unified anomaly_score (>1 = anomalous), and alerting is decoupled via vmalert. Caveat: vmanomaly is an Enterprise-licensed component (free trial available). — vmanomaly FAQ

4.2 Salesforce Merlion (unified, AutoML, distributed)

• A Python framework unifying forecasting / anomaly / changepoint detection with a shared interface, AutoML, and a PySpark distributed backend for industrial scale. — Merlion README
• Its DefaultDetector (the "balances efficiency with performance" default) is, in source, an ensemble: univariate = AutoETS (error/trend/seasonality forecaster) + RandomCutForest (online_updates=True, 100 trees, 512 max samples) + ZMS (z-score moving statistic); multivariate = VAE + RRCF. This is a concrete, production-grade realization of "cheap forecaster + streaming RRCF + z-score" with online updates enabled. — Merlion models/defaults.py source
• Anomaly scores are calibrated to z-scores and passed through a trainable threshold/calibration post-rule to cut false positives. — Merlion anomaly docs

4.3 Yahoo EGADS (Java; forecasting + detection split, designed to scale)

• Open-source Java library; "a scalable, accurate and automated anomaly detection" system compiled to "a single light-weight jar and deployed easily at scale," backing Yahoo's monitoring service that processes millions of points/sec. Extensible by design: you can drop your own model into either the time-series-model or anomaly-detection-module component. — EGADS README

4.4 LinkedIn Luminol (lightweight, score-based)

• Lightweight Python AD+correlation lib; no predefined threshold — every point gets an anomaly score. Ships a default bitmap detector (good for large data) plus exp_avg (EWMA) and derivative detectors. Good as a reference for the "cheap, threshold-free" pattern. — Luminol README

4.5 Greykite (LinkedIn; forecast-interval AD)

• Forecast-based AD over Silverkite; auto-tuned confidence intervals for the alert rate you want. — Greykite simple AD docs

5. Online training — what it concretely means here

"Online training" at 150M series must be O(1) closed-form state updates, not per-series SGD. The methods that satisfy this natively:

Key nuance — adapting without being poisoned by anomalies. Anodot describes the production policy: during an anomaly, temporarily reduce the model's learning-rate parameters (Holt-Winters α, β, γ) so the anomaly doesn't get absorbed into "normal," then restore them after the anomaly passes; a persistent change eventually gets learned. — Anodot §3.3, PMLR 71. Uber's Argos uses a median-based robust update for the same reason ("past outages and outliers must not affect the outlier score"). — Uber Argos

Streaming evaluation is a real, benchmarked thing: the Numenta Anomaly Benchmark (NAB) is built specifically for detectors that "process data in real time (not batches)" and "learn while making predictions simultaneously." — NAB, arXiv:1510.03336 · github.com/numenta/nab

6. Batch (daily) is a first-class operating mode — not a limitation

• vmanomaly scheduling: fit_every controls refit cadence. fit_every: 1d = a classic daily batch (fit on a fit_window, infer); fit_every: 1000d + infer_every: 5m = bootstrap-once + stream. You can even run backtesting schedulers over a historical period to validate a config before production. — vmanomaly FAQ
• Uber's hybrid cadence: thresholds are recomputed hourly (batch-ish) while the online part only compares incoming points against those precomputed thresholds — "extremely fast and scalable." — Uber Argos
• Implication for the requirement "online training, but daily batch OK": you do not need per-point SGD. A daily (or hourly) batch refit of a cheap statistical model, or a bootstrap-once + online-decay model, both satisfy it. The requirement is best met by stateful incremental models with a decay/forgetting factor, which are cheap and give you "online" behavior even when the heavy recompute is batched.

7. Scaling to 150M series — the recommended architecture

1. Tier 1 — cheap always-on scorer (every series, every point). Online z-score/MAD/quantile or EWMA/CUSUM + seasonal coefficients + an EVT (SPOT/DSPOT) or online-quantile adaptive threshold. O(1) state (bytes–KB/series), O(1)/point, CPU-only, horizontally shardable by series hash. This is the only stage that must run at 150M scale.
2. Tier 2 — heavier model, escalated only on flagged windows. RRCF (small forest) or a shared/global model runs only on series/windows that Tier 1 flags. This is Uber's exact production split (fast per-series "outlier detector" → heavier "outage detector" on the small remainder) and Anodot's funnel (158k single-metric anomalies → ~910 significant → 147 grouped per 4M metrics/week). — Uber Argos · Anodot §6, PMLR 71
3. Bound state to the budget. At 150M, keep Tier-1 state ≤ ~1 KB/series (~150 GB RAM, or spill to disk via the vmanomaly on-disk mode). At 10M you have ~15× headroom for richer per-series state.
4. Make tuning learned, not manual. You cannot hand-tune 150M detectors. Anodot's answer: a classifier selects the best model type per metric (~40% stationary, else sparse/step/discrete/multi-modal/irregular) and fits parameters by MLE, fully unsupervised. EGADS's answer: an AutoSensitivity/adaptive-threshold mechanism. — Anodot §3.1 · EGADS
5. Extensibility point = the scorer interface. EGADS (TSM/ADM split), Merlion (unified ModelFactory + custom models), and vmanomaly (custom model guide) all make adding a new algorithm a plug-in, not a rewrite — this is the "highly extensible" part. — EGADS · Merlion · vmanomaly custom model guide
6. Where it runs with a metrics DB. If data is in InfluxDB/VictoriaMetrics/Prometheus: vmanomaly natively reads/writes VictoriaMetrics; for InfluxDB use a stream/batch processor (or InfluxData Kapacitor UDF) that applies Tier-1 scoring per point and writes anomaly_score back. (See the sibling note for the Kapacitor detail.)

8. Options matrix

9. Pragmatic recommendation

1. Start with the cheap tier, not a fancy model: online z-score/MAD (or EWMA) + seasonal residual (Holt-Winters/ETS or the vmanomaly temporal_envelope/quantile_online) + an EVT/online-quantile adaptive threshold. This single combination satisfies cheap + 150M + online + batch-daily simultaneously and is exactly what the proven systems (Anodot, Uber, EGADS, vmanomaly online models) do.
2. Run it daily-batch or streaming via a scheduler (fit_every: 1d for offline models, or bootstrap + decay for online models), writing a unified anomaly_score > 1 metric and alerting off it.
3. Escalate with RRCF (small forest) or a shared model only on flagged windows — buys down compute at 150M while keeping precision.
4. If 150M is truly needed, engineer the state budget first (~≤1 KB/series + horizontal sharding by series); if you land at 10M, you can afford richer per-series models (RRCF, Greykite, Merlion defaults) without special effort.
5. Validate on a stratified sample (tens–hundreds of series) — you can never hand-inspect 150M — and use NAB-style streaming evaluation to measure "learn while predicting" behavior.

10. Caveats on evidence

• Vendor claims vs. independent benchmarks: the scale numbers (VictoriaMetrics 100M/billions; Anodot 120M series; Uber "tens of millions"; Yahoo "millions of points/sec") are first-party statements — documented capabilities of the systems' owners, not independent third-party measurements. They are trustworthy as existence proofs ("this scale is operated in production") but not as apples-to-apples benchmarks.
• Anodot and Uber describe architecture and design considerations, not reproducible open code. They are strong primary sources for the pattern (cheap per-series scorer + heavier escalated stage + adaptive threshold + anomaly-aware learning-rate policy), but you'd reimplement the pieces.
• RRCF state estimates are computed from the documented defaults (num_trees≈100, num_samples_per_tree≈512) and are an order-of-magnitude illustration, not a vendor-stated per-series memory figure.
• SPOT is univariate (the paper is explicit); for multivariate/contextual anomalies you combine it with a forecaster residual or escalate to a multivariate model.
• Greykite's exact AD internals are lightly documented publicly (the docs describe what it auto-tunes, not the full statistical detail); cite it for the "auto-tuned forecast interval" capability, not for a specific algorithm.

References (all primary sources, verified)

Algorithms / papers - Robust Random Cut Forest: Guha, Mishra, Roy, Schrijvers, ICML 2016 — https://proceedings.mlr.press/v48/guha16.html - RRCF mechanics (streaming, reservoir sampling, 100-tree guidance): https://docs.aws.amazon.com/sagemaker/latest/dg/rcf_how-it-works.html - SPOT (EVT streaming threshold): Siffer et al., KDD 2017 — https://www.kdd.org/kdd2017/papers/view/anomaly-detection-in-streams-with-extreme-value-theory - libspot (SPOT reference implementation, C99): https://asiffer.github.io/libspot/ - Bayesian Online Changepoint Detection: Adams & MacKay 2007 — https://arxiv.org/abs/0710.3742 - Numenta Anomaly Benchmark (streaming/online evaluation): https://arxiv.org/abs/1510.03336 · https://github.com/numenta/nab - Matrix Profile: https://www.cs.ucr.edu/~eamonn/MatrixProfile.html · https://github.com/stumpy-dev/stumpy

Production systems / case studies - Anodot (120M series, 6B points/day, seasonality + adaptive online model): Toledano et al., PMLR 71:56–65, 2018 — https://proceedings.mlr.press/v71/toledano18a.html - Uber Argos (two-stage outlier/outage, hourly dynamic thresholds): https://www.uber.com/us/en/blog/argos-real-time-alerts/ - Yahoo EGADS (TSM/ADM split, scales to millions of points/sec): https://github.com/yahoo/egads - LinkedIn Luminol (lightweight, score-based, no fixed threshold): https://github.com/linkedin/luminol

Frameworks / platforms - VictoriaMetrics vmanomaly models (online/offline, decay, on-disk mode): https://docs.victoriametrics.com/anomaly-detection/components/models/ - vmanomaly FAQ (schedulers, anomaly_score, batch/backtest): https://docs.victoriametrics.com/anomaly-detection/faq/ - VictoriaMetrics scalability (100M single-node / billions cluster): https://docs.victoriametrics.com/faq/ - Salesforce Merlion (framework + DefaultDetector): https://github.com/salesforce/merlion · default detector source: https://github.com/salesforce/merlion/blob/main/merlion/models/defaults.py - LinkedIn Greykite simple anomaly detection: https://linkedin.github.io/greykite/docs/1.0.0/html/gallery/quickstart/0200_simple_anomaly_detection.html