Algorithms & Data Structures
the bound is a claim, and it is checkable
One pass, and no room

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.
22 min read 8 figures A timestamp is stateThe answer is an estimateA guarantee names its modelTwo counts, two rankings

A HyperLogLog is the strongest argument this collection has for approximation. Over a stream of forty thousand arrivals with 4,483 distinct keys, the exact answer needs a key per key — 143,456 bits — and the estimator needs two hundred and fifty-six five-bit registers, which is 1,280. A saving of a hundred and twelve times, for an answer wrong by about three per cent.

Ask the same estimator about the last 4,096 arrivals instead of about the whole stream. The exact structure now needs 52,290 bits and the estimator needs 9,722.

Five point four.

Approximation saves 20× over a stream and 1.5× over a windowThe same estimator, asked the same question, in the two models. Over the whole stream a HyperLogLog replaces a 32-bit key per distinct item — 1,561 of them, 49,952 bits — with 512 five-bit registers, and the saving is 20 times. Over a window both structures move towards each other: the exact one shrinks, because only the keys still inside the window need keeping and there are 169 of them rather than 1,561; and the approximate one grows, because every register became a list and every entry in it carries a clock. What is left is 1.5 times. The window did not make the estimator worse. It made the exact answer cheap, and an approximation is only worth what the exact answer costs.cash register — every key49,952 bitscash register — HyperLogLog2,560 bitswindow — a stamp per live key8,505 bitswindow — HyperLogLog5,494 bits40,000 arrivals · the popular keys drift, so old keys are gone rather than rare · W = 4,0961,561 distinct in the stream · 169 in the window20× against 1.5×
Fig. 1 The same estimator, the same question, two models. Both structures move, and they move towards each other: the exact one sheds every key that has left the window, and the approximate one gains a clock for every candidate it has to keep. What is left of a saving of thirty-nine times is a saving of two.

Nothing about the algorithm changed. What changed is the thing it is being compared against, and this essay is about why both structures move and why they move in opposite directions.

Why a register cannot be a number

The estimator’s whole mechanism is a maximum. Hash each key; look at the first few bits to choose a register; count the leading zeros of what is left and call that ρ\rho; keep the largest ρ\rho any key hashing to that register has produced. A large ρ\rho is surprising, and the number of distinct keys is read off how surprising the most surprising hash was, as the essay that introduced it sets out.

A maximum over the whole stream is one number. A maximum over the last WW arrivals is not, and the reason is exactly one sentence: the largest ρ\rho may have arrived and left, and the structure has thrown away everything that would let it know what the second largest was.

The repair is due to Chabchoub and Hébrail, 2010, and it is the right one in the sense that it keeps precisely what is needed and nothing else. A register holds every arrival that could still become its maximum. An arrival (ρ,t)(\rho, t) makes every stored pair with a smaller or equal ρ\rho irrelevant — such a pair will expire no later and is no larger, so it can never be the answer again — and those are deleted.

One register of a windowed HyperLogLog: 3 arrivals that could still be its maximumRegister 110 of 256, after 40,000 arrivals with a window of 4,096. A cash-register estimator would hold one number here — the largest ρ ever hashed to this bucket — and that number is exactly what a window is not allowed to know, because the arrival that produced it may have left. So the register holds every arrival that has not been made irrelevant by a later one: a pair (ρ, stamp) survives only while no arrival after it has an equal or larger ρ. The list is therefore strictly decreasing in ρ and increasing in time, its front is the window's maximum once the expired entries are dropped, and its length is what the structure pays over the one number. 38,969 pairs have been deleted this way across the whole structure. Every row carries a stamp of 13 bits beside a ρ of 5.ρarrived atageregister 110 of 256 · window 4,096 · now t = 40,000the maximumρ = 3t = 36,0033,997 agoρ = 2t = 39,083917 agowaitingρ = 1t = 39,565435 agowaiting146 entries across 256 registers3,908 bits in all
Fig. 2 What survives in one register. The list is strictly decreasing in ρ and increasing in arrival time, which is what non-domination forces; the front is the window’s maximum once the expired entries are dropped; and each row costs a ρ and a clock.

The list’s length is bounded by the number of distinct ρ\rho values, so about twenty-five in the worst case, and in practice two or three. That bound is the reason the structure is viable at all: a register did not become an unbounded log of everything, it became a short list.

It is worth doing the arithmetic on why the lists stay short, because “bounded by the number of distinct ρ\rho values” is a worst case that never happens and the reason is a nice one. For the list to hold jj entries, the last jj arrivals at that register have to have arrived in strictly decreasing order of ρ\rho. The ρ\rho values are geometric — half of them are 1, a quarter are 2, an eighth are 3 — so a decreasing run of length three requires drawing three values in descending order from that distribution, and the probability falls fast. Averaged over a register’s live arrivals the expected length is a little under two, and the longest list in a structure of two hundred and fifty-six registers over forty thousand arrivals is typically four.

That is the same shape as the height of a skip list or the depth of a treap, and it has the same consequence: the structure’s size is a random variable whose mean is what gets quoted and whose tail is what a memory budget has to cover. The sizes reported here are the sizes at the moment they were measured, not expectations.

It also became mostly clocks. Five bits of ρ\rho against thirteen of stamp is the arithmetic the previous essay sets out, and it is why the estimator is the extreme case of the whole windowing problem — the part of it that is the answer is very small, so the part that is the time dominates.

Where a windowed structure's bits go — 30,000 arrivals, W = 4,0962 structures over the same stream, each bar the whole of its state and split into what the bits are for. Only the two rightmost bands are the answer; the rest is knowing which item and knowing when. windowed HyperLogLog holds 9,668 bits, 63% of it stamps; one stamp per live key holds 51,165 bits, 29% of it stamps. The parts are computed from each structure's own shape and are required to sum to the total it reports, so a band that had been left out of the accounting would stop the build rather than make a bar look short.windowed HyperLogLog9,668 bitsone stamp per live key51,165 bitskeysstampspayloadindexthe parts, in the order they stackwindow 4,096 · stationary Zipf51,165 bits at most
Fig. 3 The two structures on the same stream, opened up. The exact one is keys and clocks in the proportion 32 to 13; the approximate one is ρ values and clocks in the proportion 5 to 13, plus a directory. Half of one and a third of the other is time.

The exact structure got cheap, and that is the larger half

The collapse looks at first like a failure of the estimator. It is mostly not.

The smallest exact windowed distinct-counter is a map from each key to the position of its most recent arrival. Nothing older is needed: a key is in the window exactly when its last arrival is, so one stamp per key answers the question, and a key that has expired can be deleted. That structure holds the distinct keys in the window rather than the distinct keys in the stream — and those are different numbers by a lot.

stream distinct, whole distinct, in the window exact bits approximate bits saving
stationary Zipf 4,483 1,091 52,290 9,722 5.4×
one key floods a stretch 4,320 1,091 52,290 9,704 5.4×
the popular keys drift 1,561 169 8,505 3,944 2.2×

The last row is the case a windowed distinct count exists for, and it is the case where approximation buys least. That is not a paradox: a stream whose popular keys drift has a small window cardinality, an exact structure holding a hundred and sixty-nine keys is not large, and there is not much for an estimator to save.

In the cash-register model the same three streams give savings of 112, 108 and 39 times. The ratio between the two models is between eighteen and twenty-one on all three, which is the more portable statement: windowing costs the estimator about twenty times its advantage, near enough independently of what the stream is doing.

Approximation saves 56× over a stream and 4.1× over a windowThe same estimator, asked the same question, in the two models. Over the whole stream a HyperLogLog replaces a 32-bit key per distinct item — 4,483 of them, 143,456 bits — with 512 five-bit registers, and the saving is 56 times. Over a window both structures move towards each other: the exact one shrinks, because only the keys still inside the window need keeping and there are 1,091 of them rather than 4,483; and the approximate one grows, because every register became a list and every entry in it carries a clock. What is left is 4.1 times. The window did not make the estimator worse. It made the exact answer cheap, and an approximation is only worth what the exact answer costs.cash register — every key143,456 bitscash register — HyperLogLog2,560 bitswindow — a stamp per live key52,290 bitswindow — HyperLogLog12,730 bits40,000 arrivals · stationary Zipf — the control, where a window is a smaller sample · W = 4,0964,483 distinct in the stream · 1,091 in the window56× against 4.1×
Fig. 4 The same comparison on a stationary stream, where the window holds a quarter of the stream’s distinct keys rather than a ninth. The saving survives better — five times rather than two — and it is still twenty times worse than the estimator manages when nothing expires.

Where the accuracy goes

The estimator still works. It is worth showing that before dwelling on what it costs, because a structure that had merely broken would produce the same collapse and would deserve a different essay.

Error against bits for a windowed distinct count, with the exact structure markedEach point is a windowed HyperLogLog at one register count, scored at 8 moments spread over 40,000 arrivals of the popular keys drift, so old keys are gone rather than rare against an exact answer computed by machinery the estimator never sees. The window holds 169 distinct keys at the end. The vertical line is the exact structure — one timestamp per key still in the window, 8,505 bits, no error — and the horizontal distance from a point to it is the whole of what approximation buys here. It is 1.5 times at the right-hand end, against the order of magnitude the same estimator manages when it is allowed to forget nothing. Both axes are logarithmic.0.1bits of state heldmean relative errorexact, and no smallerm = 32m = 64m = 128m = 256m = 512windowedHyperLogLogwindow 4,096 · 8 sample times · truth held apart8,505 bits exact
Fig. 5 Error against bits at five register counts, scored at eight moments spread across the stream against an exact answer computed by machinery the estimator never sees. The line falls, which is the estimator doing what it does. The vertical rule is the exact structure, and the horizontal distance to it is the whole of what approximation is buying.
registers bits mean error worst error
32 1,348 13.4% 26.0%
64 2,012 7.0% 19.8%
128 2,872 3.0% 10.9%
256 3,944 4.3% 7.2%
512 5,494 3.0% 9.1%

The mean error is not monotone across the last three rows and it should not be expected to be: this is one stream scored at eight moments, and the standard error on eight samples of a quantity whose own standard deviation is 1.04/m1.04/\sqrt{m} is comfortably larger than the difference between 3.0% and 4.3%. The worst column, which is a maximum rather than a mean, falls at every step. Both are reported because reporting only the mean here would be reporting the flatter of two noisy measurements and calling it a trend.

Error against bits for a windowed distinct count, with the exact structure markedEach point is a windowed HyperLogLog at one register count, scored at 8 moments spread over 40,000 arrivals of stationary Zipf — the control, where a window is a smaller sample against an exact answer computed by machinery the estimator never sees. The window holds 1,091 distinct keys at the end. The vertical line is the exact structure — one timestamp per key still in the window, 52,290 bits, no error — and the horizontal distance from a point to it is the whole of what approximation buys here. It is 5.4 times at the right-hand end, against the order of magnitude the same estimator manages when it is allowed to forget nothing. Both axes are logarithmic.10,0000.1bits of state heldmean relative errorexact, and no smallerm = 32m = 64m = 128m = 256windowedHyperLogLogwindow 4,096 · 8 sample times · truth held apart52,290 bits exact
Fig. 6 And on the stationary stream, where the window holds a thousand distinct keys instead of a hundred and seventy, so the estimator is out of the small-cardinality regime at every register count and the curve is cleaner.

The correction that is doing more work than usual

One detail deserves naming, because it changes which numbers above are about the estimator and which are about a patch on it.

At small cardinalities the raw HyperLogLog estimate is biased, and the standard repair is to switch to linear counting — read the answer off the number of registers that are still empty — whenever the raw estimate is below 2.5m2.5m and any register is empty. Over a whole stream that regime is a brief phase at the beginning. Over a window it can be where the structure lives permanently, because the window’s cardinality is bounded by WW and by the drift, while mm is chosen for accuracy.

On the drifting stream the window holds a hundred and sixty-nine distinct keys and the plate above runs to five hundred and twelve registers. Three of those five points are in the linear-counting regime, and their accuracy is linear counting’s accuracy rather than HyperLogLog’s.

This is the same kind of observation as a bound that names its model: the accuracy claim usually quoted for HyperLogLog is 1.04/m1.04/\sqrt{m}, that claim is about the raw estimator in its own regime, and a structure asked about a window is often not in it. Choosing mm for a windowed estimator is therefore a choice about the window’s cardinality rather than about the stream’s, and it is a smaller number than the usual rule of thumb suggests.

What expiry costs to perform

Every number so far is a size, and this collection has a standing habit of asking whether the second count agrees with the first. Here it does not, and the direction is against the windowed structure again.

A cash-register HyperLogLog does one hash, one shift, one count of leading zeros and one comparison per arrival, and nothing else ever happens to it. Its work per item is a constant that does not depend on mm, on the window or on the data.

The windowed structure does the same hash, and then two things a maximum does not need. On the way in it walks the tail of its register’s list deleting the entries the new arrival dominates — cheap on average, since the lists are short, but it is a loop rather than a comparison. And on the way out something has to notice that the front of some list has expired. Expiry is not a per-register event; it is a per-structure event, and the honest implementation checks every register.

That check is what the measurements here charge nothing for. A structure that scans all mm registers on every arrival does mm times the work of the cash-register version, which at m=512m = 512 is not a constant factor anybody would ignore, and the standard repairs — expire lazily at query time, or keep the registers in a heap ordered by their front entry’s stamp — each cost something the size accounting above does not show. Lazy expiry means the structure is transiently larger than reported; a heap is another mm pointers.

So the size numbers in this essay are the smallest honest ones and the work numbers are absent, and a reader choosing between these structures should treat the second gap as real. It is the same disagreement between two counts that the machine field opened with, arriving in a place where only one of the two has ever been drawn.

The floor is not what moved

It would be tidy to say that the exact structure got cheap because there is less to know, and to leave it there. The lower bound says something more precise and worth having.

Bits of state an exact distinct-counter needs, universe 8 to 20The middle line is log₂ C(u, u/2), the exact floor: a one-pass algorithm that answers the distinct count exactly must reach a different memory state for every half-sized subset of the universe, because two subsets sharing a state give the same answer after one more key is appended and their true answers differ. The upper line is the u-bit bitmap that achieves it. The lower line is ⌈log₂(u+1)⌉, the space a plain counter takes — always below the floor, which is why no plain counter is exact. At u = 12 the floor is 9.85 bits, and a candidate holding 8 was run over all 924 subsets: two of them reached the same state, and appending one key that is in one and not the other leaves answers of 6 and 7 that it cannot tell apart.011228101214161820universe size ubits of statea u-bit bitmaplog₂ C(u, u/2)⌈log₂(u+1)⌉, a counterat u = 12: 924 subsets, 8 bitstwo collide → answers 6 and 7floor computed exactly · collision found by exhaustion at u = 12floor 9.85 bits
Fig. 7 The floor under exact distinct counting, from the previous work in this field: an exact counter over a universe of u must reach a different memory state for each of the C(u, u/2) half-sized subsets, so it needs at least log₂ of that many bits. The argument is performed rather than quoted — every subset is fed to a candidate and the collision the counting argument requires is produced.

That bound is about a universe, not about a window, and it does not become smaller when the question does. What becomes smaller is the number of states the stream can actually reach: over a window of WW arrivals the set of possible answers is bounded by WW regardless of how large the universe is, so the exact structure never has to distinguish more than (umin⁡(W,u))\binom{u}{\min(W, u)} cases and typically distinguishes far fewer.

So the honest form of the collapse is: the window did not weaken the estimator, it strengthened the exact structure’s competitor position by bounding the problem. An approximation is worth what the exact answer costs, the exact answer over a window costs a fraction of what it costs over a stream, and a saving quoted in one model transfers to the other only after both structures have been re-weighed.

One register of a windowed HyperLogLog: 4 arrivals that could still be its maximumRegister 23 of 128, after 40,000 arrivals with a window of 4,096. A cash-register estimator would hold one number here — the largest ρ ever hashed to this bucket — and that number is exactly what a window is not allowed to know, because the arrival that produced it may have left. So the register holds every arrival that has not been made irrelevant by a later one: a pair (ρ, stamp) survives only while no arrival after it has an equal or larger ρ. The list is therefore strictly decreasing in ρ and increasing in time, its front is the window's maximum once the expired entries are dropped, and its length is what the structure pays over the one number. 39,085 pairs have been deleted this way across the whole structure. Every row carries a stamp of 13 bits beside a ρ of 5.ρarrived atageregister 23 of 128 · window 4,096 · now t = 40,000the maximumρ = 6t = 37,0752,925 agoρ = 4t = 38,3941,606 agowaitingρ = 3t = 39,851149 agowaitingρ = 2t = 39,98416 agowaiting257 entries across 128 registers5,266 bits in all
Fig. 8 One register during a burst, where a single key floods a stretch of the stream. A burst does not lengthen the lists — one key hashes to one register, however often it arrives — which is the property that keeps this structure bounded and is worth seeing rather than assuming.

One list answers every shorter window too

There is a compensation for all of this that the accounting above does not credit the structure with, and it is large enough to change when the structure is worth building.

The list in a register holds every arrival that is not dominated — every pair whose ρ\rho is larger than everything after it. Ask for the maximum over the last W′<WW' < W arrivals rather than the last WW, and the answer is the front-most entry whose stamp is inside W′W'. That entry is in the list already: a pair inside the shorter window is dominated only by a later pair, and a later pair is also inside the shorter window, so the maximum over any sub-window is achieved by something the list kept.

So one structure answers every window length up to WW, at no extra state and no extra work. The query picks a cutoff and reads the front past it; the update rule does not change; nothing has to be decided in advance except the longest window anybody will ask about.

That is not a property the other windowed structures in this field have. An exponential histogram is built for one window length and cannot answer about a shorter one — its buckets have already merged away the resolution a shorter query would need — so a deployment wanting the last minute, the last hour and the last day keeps three of them and pays for all three. A register list wanting the same three keeps one, sized for the day.

Set that against the collapse this essay measures and the comparison moves. The windowed estimator loses a factor of twenty against the exact structure on a single window; against a deployment asking about several windows, the exact structure has to be replicated per window too — one map of keys to last-arrival stamps per window length, since a key can be in one window and not another. The estimator’s list is shared and the exact structure’s maps are not.

Which is the general shape worth carrying: a structure that keeps a non-dominated set rather than a summary is answering a family of questions rather than one. The extra state it holds over a plain maximum is exactly the state that makes the family available, and an accounting that prices it against a single question is charging it for something it is not doing.

The rule is the sliding-window maximum, per register

The domination rule is worth naming, because it is not specific to cardinality estimation and recognising it explains both the bound and the implementation.

Maintaining the maximum of the last WW elements of a sequence, as the window slides, is a standard problem with a standard answer: keep a deque of the elements that are not dominated — larger than everything after them — pushing at the back and popping from the front as things expire. Each element is pushed once and popped once, so the whole sweep is linear, and the deque’s contents are exactly the candidates for the maximum of any suffix.

That is precisely the structure inside each register here, with ρ\rho as the value and the arrival position as the time. The essay’s bound on the list length — the number of distinct ρ\rho values — is the deque’s bound applied to a small-alphabet sequence, and the observation two sections above that the deque answers every shorter window is the standard property of the same structure.

Naming it is worth the paragraph for a practical reason as well as a tidy one. The deque’s amortised argument is exactly the one that says the per-arrival work is O(1)O(1) despite the deletion loop — each entry is deleted once — so the loop the essay flags as “a loop rather than a comparison” is amortised constant, and the honest worry about per-item work is the expiry sweep across registers rather than the deletions within one.

What is not measured here

A sliding window over an unbounded universe with a bounded window is the easy case. Every measurement here has WW smaller than the number of distinct keys in the stream, so the exact structure genuinely benefits from expiry. Where the window is longer than the stream’s distinct count the exact structure is no smaller than it would be without a window, the estimator still pays its clocks, and the ratio is worse than any row in the table above. That regime is not drawn because it is not one anybody would build for, but a reader should know which side of it the numbers come from.

Merging. A cash-register HyperLogLog merges by taking the register-wise maximum, which is what makes it usable in a distributed system and is where a great deal of its value is. Two windowed structures merge by concatenating their lists and re-applying domination, which is correct and is not free, and the merged structure is larger than either. Nothing here measures it.

The other route. A windowed distinct count can also be built by keeping an exponential histogram per register rather than a list — trading exactness of the maximum for a bound on the list length. It is a different structure with a different error term, and quoting a size for it without building it would be quoting.

And the hash is assumed, here as everywhere. Every claim above rests on the hash turning whatever the keys are into something indistinguishable from random bits, and the windowed structure rests on it slightly harder than the cash-register one: a hash that maps a run of consecutive keys to a run of consecutive registers gives every register a contiguous stretch of arrivals rather than a scattering, and the lists’ behaviour under expiry is then a property of the key ordering rather than of the window. This collection has measured what a poor hash does to the unwindowed estimator and has not measured what it does to this one.

Where this goes next

windowed HyperLogLog4,088 bitsone stamp per live key8,775 bitsblocks of Misra-Gries18,549 bitsthe last W keys, kept131,072 bitskeysstampspayloadindexthe parts, in the order they stackwindow 4,096 · the popular keys drift131,072 bits at most 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. 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50% A count read off the leading zeros Hash every key and watch for the longest run of leading zeros. Seeing k of them is evidence of about two to the k distinct keys — an estimator with a variance so large it is worthless, and the two devices that fix it are the whole of what a cardinality sketch is. 1,00010³window length W, in arrivalsbits of state heldW bits, exactε = 0.2ε = 0.1ε = 0.05sliding-window model · 40,000 arrivals · state from the shape of the structure2,808 bits at W = 8,000 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.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

CardinalityDistinct countDominanceExpiryHash functionHonest limitHyperLogLogMeasurementSliding windowState bitsTimestampTrade off