Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Streaming model — where it appears

The setting in which data arrives once, in order, and does not fit — so whatever an algorithm did not write down is gone. Whatever an algorithm did not write down is gone, which is enforced here by a stream that refuses a second read rather than by a convention.

Named by 15 essays across 6 fields — each of them below, with the objects they name alongside it.

one summary, k = 32769one summary, k = 25608 summaries of 32, merged536worst error over the top keys, in arrivalsconcentration 1.00 — the mean share of a heavy key held by one shard8 shards · hashed · balancedmerge 536 against matched 0

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.

streaming · Merge 313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards

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.

streaming · Merge 16326412825610244096window length W, in arrivals (D = W × the mean gap)share of the counts they disagree onevenPoissonburstydrifting1 ms clock · mean gap 10 ticks · 30,000 arrivalseven: 0% at every length

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.

streaming · Window W = 256even256–256Poisson225–285bursty256–256drifting79–1,736items held inside the time windowD = 2.56 s · 1 ms clockW would be 256, always

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.

wrong · Window 71 s60 ticks11100 ms600 ticks1410 ms6,000 ticks171 ms60,000 ticks270.001 ms60,000,000 ticksclock resolutionbits per stamp⌈log₂ 2D/r⌉no arrival rateappears in itD = 60 s · key 32 bitscomputed, not measured

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.

space · Window decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions

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.

streaming · Decay above 0.01 of the stream · 13 really areone pass: 18 candidatestwo passes: 13 keys, exactly the heavy ones123456789101112131415161718128 counters · carry 1,376 bits5 of 18 spurious

The pass that was never a parameter

One pass is the streaming model's defining restriction, and this collection has enforced it by making 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.

bounds · Pass fades a lazy table computed382,976fades an eager table would compute3,830,256fade multiplications (log scale)11,968 evictions, each comparing all 32 counters at one instant32 counters · half-life 4 s · bursty10× fewer

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.

practice · Decay 10³10⁴10⁵10⁶passes over the datapeak bits of stateone pass, exact: 1,048,576 bitsradix, uniformsample, uniformradix, paretosample, paretoevery point exact · 32,768 values320 bits at best

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.

space · Pass read from the start40,000 readsa ring of 4,096 keys and 4,096 stamps184,320 bitsread from the end4,096 reads792 counters, no stamps50,688 bitsitems readsame answer: 1×700, 2×341, 3×224…W = 4,096 · φ = 0.02 · stationary Zipf9.8× fewer reads, same answer

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.

floors · Pass universe 0…11 · prefixes of 6 · candidate keeps 9 bitsthe two prefixes that collideA01234567891011B01234567891011first differencesame state — the candidate stores "7" after boththen both read the same suffix -1, -2, 12, 13, 14true median of A3true median of B4and one answer for both924 prefixes · floor ⌈log₂ C(12,6)⌉ = 10 bits10 bits collide on none

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.

floors · Pass shard 1 · 120 → 119shard 2 · 121 → 120shard 3 · 120 → 120shard 4 · 121 → 120shard 5 · 119 → 118shard 6 · 124 → 123shard 7 · 121 → 120shard 8 · 122 → 121floor, in arrivalsnaive: tail ÷ kfixed pointmeasuredstationary Zipf · round · k = 321.006× the measured floor

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.

streaming · Merge ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14%

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.

space · Space 10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21×

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.

streaming · Rank 00.2500.5000.7501010203040age of an arrival, secondsweight it carries nowexponential, half-life 4.0 sbackward polynomial, α = 2, scale 4.0 sforward, β = 2, landmark 20 s backforward, β = 2, landmark 160 s backdotted: half weightweights at the moment of reading

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.

streaming · Decay

Named alongside it

The objects these essays reach for when they reach for this one.

State bitsGuaranteeMeasurementTimestampArrival processHeavy hitterTrade offEstimatorHonest limitMisra–GriesOne passSliding window

All concepts