The summary that has to forget

Every structure in this field so far has one thing in common that nothing has drawn attention to: it only ever accumulates. A counter goes up, a register bank’s registers only rise, a sketch’s cells take another addition. Even the turnstile model’s decrements are additions of negative numbers.

Now change the question. Not “how many ones have there been” but “how many ones were there in the last thousand arrivals”.

A counter cannot answer it. Not because it is too small — a counter is exact and costs seventeen bits — but because it has no record of which of its increments are about to become old. To decrement correctly at time $t$ it would have to know what arrived at time $t - W$, and it did not keep that.

The model, and why it is different from the others #

The sliding-window model is the fourth dial in this phase and it is the only one that changes what the structure has to be rather than how well it does.

Turning on signed updates left Count-Min working and broke its guarantee. Weakening the hash family left the tug-of-war estimator working and broke its variance. Turning on expiry leaves nothing working at all: an exact counter, a Count-Min sketch and a HyperLogLog are all equally unable to answer a windowed question, and no amount of extra state fixes it, because the missing information was discarded at arrival time rather than compressed.

So this is the only model in the phase whose structures are new constructions rather than old ones re-examined.

The obvious repairs, and why they fail #

Keep the window. $W$ bits for a bit stream, exact, and the next essay proves that is optimal for an exact answer. At $W = 10^6$ it is a megabit per counter and there are usually thousands of counters.

Keep a counter and subtract on expiry. This requires knowing the expiring item, which is keeping the window under another name.

Keep a counter per block of time. Divide the stream into blocks of $W/k$ arrivals, keep the last $k+1$ block counts, and report the last $k$ plus a share of the oldest. This works and it is the right idea, and the state is $k$ counters of $\log W$ bits each with error $1/k$. The exponential histogram is this idea improved, and the improvement is worth the extra machinery: fixed blocks spend the same number of bits on the recent past as on the distant past, and the distant past is the only part with any uncertainty in it.

The structure #

Datar, Gionis, Indyk and Motwani’s exponential histogram keeps a list of buckets, newest last. Each holds a size, always a power of two, and the timestamp of the most recent arrival it covers.

On a one: append a bucket of size 1 with the current timestamp. Then, while more than $k+1$ buckets share a size, merge the two oldest of that size into a single bucket of twice the size carrying the newer of their two timestamps. Then discard any bucket whose timestamp has left the window.

On a query: sum every bucket’s size, and subtract what is genuinely unknown about the oldest.

Three properties fall straight out of that.

Sizes are powers of two, because merges only ever combine two equal buckets. There are at most $k+1$ buckets of each size, which is the invariant the merging maintains. And sizes grow geometrically towards the past, so the number of buckets is about $k \log_2(N/k)$ where $N$ is the count in the window.

Here is one, in full: window of 400, $\varepsilon = 0.2$, so $k = 5$.

32 · 16 16 16 16 16 16 · 8 8 8 8 8 8 · 4 4 4 4 4 4 · 2 2 2 2 2 · 1 1 1 1 1

Twenty-nine buckets, after 1,764 merges. They sum to 200; the estimate is 199.5; the true count in the window is 200. The structure holds 406 bits against the window’s 400 — at this window length it is not yet a saving, which is the subject of a later essay.

Twenty arrivals, in full #

At $k = 2$ — at most three buckets of any size — the first twenty ones produce this, oldest bucket on the left:

Twelve merges in twenty arrivals. The interesting steps are the ones where a row is shorter than the row above it: at the fourth arrival a fourth bucket of size 1 would have appeared, so the two oldest merged into a 2. At the tenth, that merge produced a fourth 2, which merged into a 4 — one arrival, two merges, a cascade.

The list is a number written in a strange base. Reading it as sizes, 4 4 4 2 2 2 1 1 is twenty, and the constraint that at most $k+1$ buckets share a size is what stops the representation from being either the unary one (all ones, exact, $N$ buckets) or the binary one (one bucket per power, $\log N$ buckets, and a hopeless oldest bucket). $k$ interpolates between those two extremes and the interpolation is the whole design.

Why powers of two #

Nothing forces the sizes to be powers of two, and the choice is worth defending because a different ratio is available.

Merging two equal buckets doubles the size, so the sizes that arise are powers of two, and the number of distinct sizes is $\log_2$ of the count. A ratio of $r$ instead — merge $r$ buckets at a time — gives $\log_r N$ distinct sizes and therefore fewer buckets, at the cost of a coarser oldest bucket. It is the same trade a dynamic array makes when it chooses its growth factor, and it comes out the same way: two is a good default and nothing dramatic happens on either side of it.

The part that is not a free choice is the $k$ buckets per size. That number is what bounds the oldest bucket as a share of the total, and it is the accuracy dial. Changing the ratio changes the state by a logarithmic factor; changing $k$ changes the error directly.

The whole error is one bucket #

This is the part worth internalising, because it makes the accuracy argument trivial.

Every bucket except the oldest lies entirely inside the window: its timestamp is inside, and all its ones arrived no later than that. The oldest bucket is the only one that straddles the boundary — its timestamp is inside, so it has not been discarded, but the ones it absorbed may have arrived before the window opened.

So the only uncertainty in the answer is how many of the oldest bucket’s ones have already left, which is somewhere between zero and its size minus one. The estimate splits the difference, and the error is at most half the oldest bucket’s size.

The invariant then finishes the argument. There are at least $k$ buckets of every size smaller than the oldest one’s, so the total is at least $k$ times the oldest bucket’s size, so the error is at most $1/(2k)$ of the total. Set $k = \lceil 1/\varepsilon \rceil$ and the relative error is at most $\varepsilon/2$.

That last factor of two is not in the usual statement of the bound and it is exactly what the measurements show.

Every row is at or just under half the bound, across a window of a thousand and twenty thousand arrivals. A bound that is loose by exactly two, at every setting, is a bound that has dropped a factor rather than one that is being generous.

A half that should have been a half of one less #

The estimate above subtracts $(\text{size} - 1)/2$ from the total, and the textbook form subtracts $\text{size}/2$. The difference is invisible almost everywhere and is wrong.

A bucket of size one holds exactly one arrival. If its timestamp is inside the window then that arrival is inside the window, and there is nothing uncertain about it. Charging half of it is charging uncertainty to a bucket that has none.

On a busy window this is a rounding error. On a quiet one it is not: a window holding five ones has all of them in buckets of size one, the structure knows the answer exactly, and the textbook estimate reports 4.5 — a 10% error from a structure that is keeping every arrival separately.

It was found by a sweep whose smallest window was quiet, and it is the only place in this field where a measured error exceeded what the bound permitted. Both forms are correct as bounds; only one of them is correct as an estimate.

Read the two together and the parameter stops being a dial and becomes a picture. $k$ decides how many buckets of each size are allowed to stand before two of them merge, so it decides how large the oldest bucket is as a share of the window — a tenth of it at $k = 10$, half of it at $k = 2$ — and the half of that bucket the estimate cannot place is the $1/(2k)$ the invariant bounds. The staircase in each of these plates is the bound, drawn.

What the merging costs #

Merges are frequent — 1,764 of them over four thousand arrivals in the histogram above — and each is a constant amount of work, so the amortised cost per arrival is a small constant.

The accounting is the same one a dynamic array’s doubling uses, and it comes out the same way: a bucket of size $2^j$ can only be created by merging two of size $2^{j-1}$, so the total number of merges over a stream of $N$ ones is at most $N \sum_j 2^{-j} < N$. Fewer than one merge per arrival, on average, however the arrivals fall.

The worst individual arrival is a cascade: a one arrives, forces a merge at size 1, which overflows size 2, which overflows size 4, all the way up. That is $O(\log N)$ work for one arrival and it is the same spike a doubling array shows at a power of two — an amortised bound and a per-operation bound describing genuinely different quantities, one field along.

The recent past is exact and the distant past is not #

There is a property of this structure that the error bound does not convey and that matters in practice: the resolution is not uniform in time.

The newest buckets are of size one, so the structure knows the last few arrivals exactly. Buckets double towards the past, so an arrival from long ago is known only to within the size of the bucket it landed in. Everything the structure has forgotten, it forgot about the distant past.

For a windowed count that is precisely the right allocation, because the only uncertainty in the answer is at the boundary and the boundary is old. For a query about when something happened it is the wrong allocation and the structure has nothing to offer: it can say the window holds two hundred ones and cannot say whether they were spread evenly or arrived in a burst forty arrivals ago.

The block-counter version of this idea has the opposite profile — uniform resolution everywhere, which spends bits on recent detail nobody asked for. The measured comparison at equal error is that the histogram holds $k \log_2(N/k)$ buckets where blocks hold $k$ counters of $\log_2 W$ bits, and which is smaller depends on $N$ against $W$; the histogram wins when the ones are sparse, because it does not pay for empty blocks.

Which timestamp a merge keeps, and why #

A merge combines two buckets and keeps one timestamp — the newer of the two. That is stated above as part of the rule and it is a decision with a direction, worth pulling out because it settles which way the structure is wrong.

A bucket covers arrivals from its oldest to its newest. Stamping it with the newest means it survives until every one of its arrivals has left the window, so it is retained for a while after some of them have expired — the structure counts ones that are gone, and the estimate is high. Stamping it with the oldest would discard it as soon as its first arrival expired, so ones still inside the window would be thrown away and the estimate would be low.

Both are bounded by the same quantity — the bucket’s size — and the choice is purely which direction to be wrong in. The published rule takes the newer, so the raw sum of the buckets is an over-estimate, and the subtraction of half the oldest bucket is what turns a one-sided answer into a centred one.

That is the same decision as everywhere else in this field, arriving in an unexpected place. A structure whose caller must never under-count — a rate limiter, a quota, an alarm on a threshold — should report the raw sum and keep the one-sidedness the timestamp rule already provides. A structure whose answer is a display should subtract and be centred. The two answers differ by half a bucket and are available from the same state, and only one of them is usually offered.

The oldest bucket could carry a second timestamp #

The whole error is one bucket, which makes the target for any improvement obvious: shrink what is unknown about the oldest bucket without keeping more of them.

There is a way, and it costs one timestamp. Store, for the oldest bucket only, the stamp of its earliest arrival as well as its latest. The bucket’s ones then have a known time span, and the fraction of that span lying inside the window is computable — so instead of assuming half the bucket has expired, the estimate can interpolate.

On a stream whose arrivals are roughly evenly spread the interpolation is much better than the half. A bucket of thirty-two spanning two hundred arrivals of which forty are outside the window has lost about a fifth of its ones, not a half, and the difference is six counts on an answer of two hundred.

Two honest caveats, and they are the reason this is not simply an improvement.

It is not a bound. The ones inside a bucket may be clustered at either end, so the interpolation can be wrong in either direction by up to the bucket’s size — which is exactly the uncertainty the half was there to acknowledge. The right arrangement keeps both: report the interpolation as the point estimate and the untouched $[\,\text{total} - \text{size},\ \text{total}\,]$ as the bracket, which is the same two-numbers-per-answer arrangement a counter-based summary can offer and for the same reason.

And it costs a stamp on one bucket rather than on all of them, which is thirteen bits against a structure of four hundred. That is a favourable trade only because the error is concentrated in one place; a structure whose uncertainty was spread over every bucket would have to pay for every one, and the concentration this essay is about is what makes the repair cheap.

What it is not #

It is not linear. The state is not a sum of updates: it is a set of buckets with timestamps, and merging two histograms of different windows is not defined. So the model list for this structure is the sliding window and nothing else, which is exactly the opposite of the sketches two essays back — they are valid in every model that does not expire, and invalid in the one that does.

It does not count keys. Everything above is about a bit stream: how many ones in the last $W$. Windowed versions of the frequency and cardinality questions exist and are built from this idea plus per-key or per-register timestamps, and they are not implemented here.

It cannot be un-asked. The window length is baked into the expiry rule, so the same arrivals processed under two window lengths need two structures. Where several windows are wanted — the last minute, hour and day, which is the ordinary requirement — that is three histograms and three times the state, and there is no sharing between them worth having, because the coarse structure has already merged away the detail the fine one needs.

It cannot be asked about an arbitrary interval. The window is fixed when the structure is built. A query for “the last hundred” from a structure built for the last thousand has no answer better than a proportion, because the buckets that would resolve it have already been merged.