Sliding window — where it appears
Named by 16 essays across 7 fields — each of them below, with the objects they name alongside it.
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 dictionary that builds itself
LZSS contains no probability, no frequency table and no entropy calculation. Its entire model is a window of recent text and its only move is to say "the next nine symbols are the ones that appeared 1,200 positions ago". On a stream whose zeroth-order floor is 3.89 bits per symbol it spends 2.11, and widening its window past 4,096 makes it worse rather than better.
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 model a bound was quoted in
Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.
What a window costs in bits
The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.
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 summary that has to forget
Every structure in this field so far accumulates. Ask instead for the count over only the last thousand arrivals and no counter will do, because a counter has no record of which of its increments are old — and the repair is a row of buckets whose whole error is the oldest one.
The bits that say when
A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.
The floor under a window
An exact count of the ones in the last W arrivals needs W bits, and the argument is a pigeonhole that can be performed rather than quoted — 1,024 windows, an eight-bit state, the colliding pair produced, and the two answers it cannot tell apart.
A register that became a list
HyperLogLog replaces a key per distinct item with a five-bit register, and over a whole stream that is a saving of a hundred times. Ask it about the last four thousand arrivals instead and the same comparison against the same exact structure comes out at five. The estimator did not get worse. The exact answer got cheap.
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.
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.
The count that outlives its arrivals
A Misra-Gries counter holding six thousand is not a record of six thousand arrivals. It is a number that has been added to and taken from, and nothing in the structure says when any of it happened — so when the key stops arriving the counter stays, and goes on reporting a key with nothing in the window as the heaviest thing in it.
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.
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.
The sampler that cannot alias
A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.
Named alongside it
The objects these essays reach for when they reach for this one.
State bitsExpiryMeasurementArrival processTimestampTrade offBurstinessExponential histogramGuaranteeHonest limitTime windowOccupancy