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

Occupancy — where it appears

How many items are inside a window at an instant, which is a constant in the arrival-counted model and a random variable in a time window. It is the quantity a structure holding the window has to be sized for, and sizing from the mean rather than the peak undersizes badly.

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

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 0%25%50%75%100%1×1.5×2×3×4×6×shareheadroom over the mean occupancyoverflowingstanding idledrifting · 4.0 s window · 100 Hz47% overflow at the mean

Sized for a rate that does not hold still

A four-second window on a stream at a hundred arrivals a second holds four hundred items on average and between 105 and 2,169 when the rate moves. An allocation set at that average overflows at 47 per cent of instants while 35 per cent of it stands empty, which is the same decision failing in both directions at once.

practice · Window even5.1 s – 5.1 s1.00× · dispersion 0.00Poisson4.7 s – 5.5 s1.16× · dispersion 0.70bursty4.5 s – 4.5 s1.00× · dispersion 0.57drifting565 ms – 14.8 s26.14× · dispersion 849.57duration one block covered4,096 arrivals in 8 blocks · 100 Hz · 1 ms clock26.1× on the drifting stream

The window that is even in the wrong currency

A window of four thousand arrivals in eight blocks retires a block every 5.1 seconds on a steady stream and anywhere between 0.57 and 14.8 seconds on a stream whose rate moves. The structure cannot tell, because it is counting arrivals, and the alert written against it is in seconds.

streaming · Window 1.821251.951.431752.731.302253.521.292503.911.183755.861.005128.00longest block ÷ shortestarrivals per block, and bursts per blockpart of a bursta whole numberbursts of 64 · 8 blocks · 20,000 arrivalsdispersion 0.57 and a ratio of 1.00

The boundary that hides the burst

A window whose blocks hold five hundred and twelve arrivals reports a perfectly even stream — every block the same duration to the tick — while the arrivals it is retiring have an index of dispersion of 0.57. Move the block to a hundred and twenty-five and the same stream varies by 1.8 times.

wrong · Window

Named alongside it

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

Arrival processBurstinessTime windowSliding windowClock resolutionMeasurementExpiryState bitsStreaming modelTemporal resolutionTimestampAliasing

All concepts