Detecting a Burst of Events in a Stream

A burst is a rate that is high relative to what the rate usually is. All the difficulty is in “usually”, and a threshold derived from a baseline and its spread is the only version of this that survives contact with a seasonal stream.

What counts as a burst

Fix the terms first, because most confusion here is definitional. You are counting events in buckets of some width w, and comparing each bucket’s count to an expectation. Three parameters completely determine the detector: the bucket width, the baseline model, and the threshold. Nothing else you do matters as much as those three, and only the third one is usually tuned.

Bucket width sets what you can see. A one-second bucket detects a burst that lasts a second and is dominated by noise; a one-hour bucket detects sustained shifts and cannot see a 90-second spike at all, because forty extra events spread into a bucket that normally holds 3,600 do not move it. The rule of thumb that follows from that: set the bucket to roughly the duration of the shortest event you care about, and if you care about several durations, run several detectors rather than compromising on one. Note that a bucket is a tumbling window, and it inherits that window’s boundary problem: a burst straddling a boundary is split across two buckets and may clear the threshold in neither. Running two staggered detectors offset by half a bucket is the cheap fix.

Deriving a threshold

Assume you have measured a stream over a quiet week and found a mean of μ = 400 events per minute with a standard deviation of σ = 35. Both are properties of your data, and the whole point is that they are measured rather than assumed. A threshold of the form μ + kσ then has a meaning you can state.

baseline           mu = 400 events/min,  sigma = 35

k = 2   threshold = 400 + 70  = 470
k = 3   threshold = 400 + 105 = 505
k = 4   threshold = 400 + 140 = 540

If the counts were normally distributed, the one-sided exceedance
probabilities would be:

k = 2   0.0228   -> 1 bucket in    44
k = 3   0.00135  -> 1 bucket in   741
k = 4   0.0000317 -> 1 bucket in 31,560

At one bucket per minute, 1,440 buckets per day:

k = 2   ~32.8 false alarms per day
k = 3   ~1.94 false alarms per day
k = 4   ~0.046 false alarms per day  (about one every 22 days)

That table is the argument for deriving thresholds rather than picking them. “Two sigma” sounds strict and produces an alert every 44 minutes. The jump from k = 3 to k = 4 costs you almost nothing in sensitivity — 505 to 540 events, a 7% difference — and reduces false alarms by a factor of 42. Whenever someone asks why the pager is noisy, this arithmetic is usually the answer, and it is usually never been done.

To use it online you need μ and σ maintained continuously, not recomputed from a fixed historical week. An exponentially weighted moving average and variance do this in constant memory: with a smoothing factor α, μ ← αx + (1−α)μ and the EWMA variance updates from the same residual. The choice of α is the choice of how quickly the baseline forgives a change — small α means a burst that lasts an hour eventually becomes the new normal and stops alerting, which may be what you want or may be exactly the failure. Freeze baseline updates while an alert is firing if it is not.

Why the Poisson assumption fails

The textbook model for counts of independent events is Poisson, under which the variance equals the mean. That is a strong claim: at μ = 400, Poisson predicts σ = √400 = 20. The measured σ above was 35, which is 75% higher, and the discrepancy has a name — overdispersion — and a cause.

Real event streams are not independent arrivals. One user action produces a burst of correlated events; one retry policy turns a single failure into five; one deploy shifts the rate for everyone at once. The usual model that accommodates this is the negative binomial, which is a Poisson whose rate is itself random, and its extra parameter is exactly the amount of clustering. The practical consequence for a threshold is simple and important: never compute σ as √μ from the mean. Measure it. A detector built on the Poisson assumption over an overdispersed stream sets its threshold at 400 + 3(20) = 460 instead of 505, and fires roughly seventeen times more often than intended.

The second failure is seasonality. A stream with a daily cycle has a global σ dominated by the difference between 03:00 and 15:00, not by minute-to-minute variation, so a single global threshold is far too loose at night and far too tight at peak. The fix is to model the baseline per time-of-day — a separate μ and σ per (weekday, hour) cell is crude, cheap and works — or to detect on the residual after subtracting a seasonal component rather than on the raw count.

The multiple-comparisons problem

The false-alarm arithmetic above was for one stream. Detectors are rarely deployed on one stream; they are deployed per service, per endpoint, per log template, per customer. If you run the k = 3 detector across 500 series, the expected false alarms per day is not 1.94, it is 500 × 1.94 = 970. The detector did not get worse. You ran it 500 times.

There are three honest responses. Raise k with the number of series, which is a Bonferroni-style correction and costs sensitivity. Require persistence — two or three consecutive buckets over threshold — which cuts independent false alarms roughly by the square or cube of the per-bucket rate while delaying detection by a bucket or two. Or aggregate first and drill down after, alerting on the total and using per-series scores only to explain an alert that already fired. The third is usually best, and it is the design behind most alerting that people do not turn off.

State-based detection

Threshold methods answer “is this bucket high?”. A different formulation asks “what sequence of underlying rate states best explains the whole observed stream?”, which automatically prefers a small number of sustained bursts over a scattering of single-bucket excursions. Jon Kleinberg’s “Bursty and Hierarchical Structure in Streams” formalises this as an automaton with states of geometrically increasing rate, where entering a higher state carries a cost. The optimal state sequence is found by dynamic programming, and the cost parameter is what stops the model flipping states on every noisy bucket.

The properties worth knowing: it produces intervals with start and end times rather than a stream of independent alerts, it has an intensity level rather than a boolean, and it is naturally hierarchical, so a long moderate burst can contain a short intense one. The cost is that the classic formulation is offline — it needs the whole sequence — so online use means running it over a trailing buffer. For alerting, the EWMA threshold is what fires; for post-incident analysis and for ranking “what was unusual yesterday”, the state-based view gives a far more readable answer.