Streaming model — where it appears
Named by 22 essays across 6 fields — each of them below, with the objects they name alongside it.
The state a merge is standing in for
A merge of eight summaries of thirty-two counters is wrong by 536 where one summary of thirty-two is wrong by 769, which reads as merging helping. One summary of two hundred and fifty-six counters — exactly what the eight were holding between them — is wrong by nothing at all.
The partition the analysis did not mention
Space-Saving and Misra-Gries are the same structure under a stream, related by subtracting one number. Sharded eight ways and merged, one of them is wrong by 313 where the other is wrong by 927 — and swapping how the arrivals were assigned to machines reverses which is which.
A window that is a duration
Nobody asks for the error rate over the last four thousand and ninety-six requests. They ask for the last five minutes. The two are the same question exactly when the arrivals are evenly spaced, and on a stream whose rate drifts they disagree about fifty-seven per cent of the counts.
The window that is not full
A structure sized for a window of 256 items meets a stream that hands it 1,736 at the worst instant and 79 at the best. Occupancy was a constant in the model the sizing came from, and every per-item bound in that model quietly assumed it.
The clock that cannot see the burst
A stream generator asked for a burst ten times faster than its mean rate, on a clock whose resolution was the mean gap, produced a perfectly even stream — index of dispersion 0.00, for something called bursty. Nothing had gone wrong except that the instrument could not represent what it was being asked to measure.
The counter with no window in it
A counter that fades by half every H settles, on a steady stream, at exactly the count of a window of 1.44H. That correspondence holds in the mean, on a steady stream, and nowhere else — and it is the reason a decayed counter is not an estimate of a windowed count for any window.
The pass that was never a parameter
One pass is the streaming model's defining restriction, and the usual way to enforce it is to make a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.
The fading nobody computes
Twelve thousand arrivals into thirty-two decayed counters cost 382,976 fade multiplications. An implementation that aged every counter on every tick would have cost 3,830,256, and the ratio is exactly the mean gap between arrivals — not a coincidence, and the reason the family is deployable.
What a second pass buys
Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.
What a pass costs when it is a file
The streaming model trades passes for memory along n to the power one over p, and it never says what a pass costs. On a file a pass is a read of every block, and it cannot run in less than one block of memory. Charge both and the trade nearly disappears: the median of four million keys takes three passes at two blocks of memory and two passes at four, and writing the surviving interval out makes the third pass cost sixteen blocks instead of four thousand. On a heavy tail the same habit nearly doubles the bill.
The pass that runs the other way
Exact heavy hitters over the last 4,096 of 40,000 arrivals cost 40,000 reads and a ring of 4,096 keys and stamps read forwards, and 4,096 reads with no stamps read backwards. Every lower bound in the sliding-window model is a bound about an access pattern, and the word doing the work never appears in the statement.
A floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.
The floor a histogram already knows
A summary of thirty-two counters settles at a smallest counter of 119, and the number can be computed from the shard's key frequencies before a single counter is allocated. The obvious way to compute it is wrong by a factor of two, and the reason is that the heavy counters carry no error at all.
The tuples a summary does not report
A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.
The period that is not a promise
Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.
A decay measured from where it started
An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.
What a heavier tail actually buys
Four decays, each tuned until it is equally quiet on a stream with nothing happening, then given one burst. At a burst of three hundred they see it for 54, 63, 68 and 104 seconds — indistinguishable. At nine thousand the exact polynomial reaches 384 seconds and the exponential 156. The shape of a tail does not decide how far back a scheme can see. It decides how fast that distance grows with the size of the event, and the exchange rate is the reciprocal of the exponent.
A detector that learns its own quiet
A burst detector built from a fast decayed counter needs a threshold, and the one it was measured with came from sixty independent runs of the background — an oracle no deployed system has. Two counters and a running mean square of their difference can supply it from the stream itself, and on a stream that does not move they hit a 5% false-alarm rate at every setting tried. What they lose is the burst: a scale that learns every reading learns the burst as noise and forgets it in 20 to 40 seconds whatever its size. Holding the scale while alarmed brings the oracle's horizon back for small bursts, turns a slow drift into an alarm that will not stop, and still cannot see past the lag at which the slow counter holds more of the burst than the fast one.
The clock a burst cannot outlast
A burst detector that holds its scale while alarmed keeps a burst visible to a ceiling set by two half-lives, and cannot stop alarming on a slow drift. The repair proposed for it was a schedule: learn again once an excursion has outlasted anything a burst could produce. Timed by how long the alarm has lasted, the schedule changes almost nothing, because on a gentle rise the alarm breaks every few seconds and the clock never reaches the ceiling. Timed by how long the difference between the counters has stayed positive, it keeps every burst to within about a second of the ceiling and falls below the target false-alarm rate on steep drifts — and one quantity, the drift's offset measured in spreads of the difference, says where it still fails.
The slope the slow counter already shows
A burst detector built from a fast and a slow decayed counter reads a steady rise in its background as an offset in their difference, β(R − 1)H/ln 2, and alarms on it. Every repair so far waited the offset out. This one subtracts it: the slow counter's own change over one slow half-life is a reading of the slope, and the offset follows from it. At R = 16 the corrected detector alarms on 5.5% to 7.8% of readings on rises that make the held scale alarm on 11% to 63%, and it costs a burst at most 3.7 seconds of detection. The estimate has to be quick: four times slower, it has recovered only 71% of the offset when alarms start to count.
The rise the correction kept subtracting
A burst detector that subtracts a rising background's offset, read off its own slow counter, goes on subtracting it after the rise has stopped. The prediction was a deficit for about one slow half-life that would cost bursts of 300 arrivals. Measured, the deficit is deeper and longer: down to 1.46 spreads below zero, below half a spread for seventeen minutes after a 40% rise. Bursts of 300 are never missed. What the deficit costs is small bursts — 30 arrivals caught 27% of the time where the rise saw 77% — and a fifth of a large burst's visible time.
A check as slow as what it checks
A burst detector that subtracts a rising background's offset goes on subtracting it after the rise ends, and loses small bursts in the trough that opens. Capping the subtraction by what the difference itself shows, averaged over one slow half-life, was predicted to close the trough to under half a spread. It lifts it from 1.46 spreads to 1.24, because that average is as late as the estimate it checks. Averaged over a quarter of the time it lifts it to 0.70 and catches small bursts in the trough more often than any other design but the one that alarms on a fifth of its readings. Neither cap helps after a large burst, which every slope correction reads as a rise.
Named alongside it
The objects these essays reach for when they reach for this one.
State bitsEstimatorHonest limitExponential decayHalf lifeGuaranteeMeasurementDesign parameterTimestampFalse alarmTrade offArrival process