The thread: A timestamp is state
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 other axisThe 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.
One pass, and no roomThe 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.
One pass, and no roomA 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.
StructuresThe 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.
One pass, and no roomThe 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.
One pass, and no roomA 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.