The floor under a summary

The first floor on this site counts outcomes. A comparison sort must be able to distinguish $n!$ orderings; each comparison distinguishes two cases; so no comparison sort makes fewer than $\log_2(n!)$ comparisons. It is exact, computable, and it bounds a resource — comparisons — that the algorithm spends.

The floor here counts something else. It bounds a resource the algorithm holds, and it is the same argument with memory states in place of outcomes.

The argument, in four lines #

Fix a universe of $u$ keys. Restrict attention to streams that consist of the elements of some subset $S$ of size $u/2$, in any order.

Suppose a one-pass algorithm answers the distinct count exactly, and suppose two different such subsets $S \ne T$ leave it in the same memory state. Take a key $x$ that is in $S$ and not in $T$ — one exists, because the two subsets are the same size and are different — and append it to both streams.

From that point on the algorithm sees identical input from identical state, so it ends in identical state and gives an identical answer. But the true answers differ: $S \cup \{x\}$ has $u/2$ distinct keys and $T \cup \{x\}$ has $u/2 + 1$.

So no two of the $\binom{u}{u/2}$ subsets may share a state, the state must take at least that many values, and the memory must hold at least $\log_2\binom{u}{u/2}$ bits.

Nothing in that depends on how the algorithm works. It is not about hashing, or about which statistic is kept, or about cleverness — it is a counting argument over memory states, and it applies to every algorithm at once in exactly the way the sorting floor applies to every comparison sort at once.

Performing the pigeonhole #

Quoting a pigeonhole argument is cheap. The habit this site runs on is that a claim gets a test it could fail, so the collision is found rather than asserted.

At $u = 12$ there are $\binom{12}{6} = 924$ half-sized subsets and the floor is $\log_2 924 = 9.85$ bits. A candidate algorithm holding eight bits — a bitmap of the first eight keys, which is a reasonable thing for a small exact counter to keep — is run over all 924, its final state recorded for each, and the states compared.

Two subsets collide. The witness is complete: the two streams, the shared state, the key to append, and two true answers of 6 and 7 that the algorithm answers identically. That is a refutation rather than an existence claim.

The second half of the check is the one that makes the first mean anything. The same exhaustive search is run against a candidate holding twelve bits — enough for the whole universe — and it must not collide, and it does not: 924 subsets, 924 distinct states. A floor that fired on everything would be a bug rather than a bound, and this is the check that says so. A third candidate, one that keeps only the running count, collides immediately, which it must.

What the number looks like #

$\log_2\binom{u}{u/2}$ is $u - \tfrac12\log_2 u - O(1)$ — linear in the universe, with a small logarithmic discount.

The bitmap is within a few per cent of the floor at every size, so the floor is essentially tight and the obvious algorithm is essentially optimal. There is nothing to find here — which is the useful conclusion, because it says the exact problem is closed and any progress has to come from changing the problem.

That is the same shape as the sorting floor’s aftermath. How close anything gets to the floor measures the gap between the best sorts and $\log_2(n!)$ and finds it small, and the interesting work moves to constants and to different models rather than to better comparison sorts.

Changing the problem #

Every structure in this phase gets under that floor, and none of them violates it. They answer a different question.

Allow the answer to be within a relative $\varepsilon$ and to be that wrong with probability at most $\delta$, and the requirement drops from linear in the universe to $O(\varepsilon^{-2} + \log u)$ bits — a few thousand, permanently, whatever $u$ is. A HyperLogLog of 5,120 bits counts distinct keys drawn from a universe of four billion to within 3.4%, and the exact floor for that universe is four billion bits.

The size of that gap is the whole justification for the field. It is not a marginal saving; it is the difference between a structure that fits in a cache line and one that does not fit anywhere.

The approximate floor, and what is not claimed #

There is a lower bound for the approximate problem too: $\Omega(\varepsilon^{-2})$ bits, from Indyk and Woodruff and sharpened since, and it is a communication-complexity argument rather than a counting one.

It is not demonstrated here. Quoting it while pretending to have measured it would be exactly the failure this site exists to avoid, and the argument is not one that a small exhaustive search performs. What is measured is the shape: every estimator in this field climbs an $\varepsilon^{-2}$ curve, and none of them climbs a cheaper one.

That distinction is worth making carefully, because it is the difference between two kinds of statement. The exact floor above is a theorem verified here at small $u$, by exhaustion. The approximate floor is a theorem quoted here, alongside a measurement of whether the structures behave as though it binds them. Both are honest and they are not the same, and the plate for each says which it is.

The measured version: fitting log-bits against log-accuracy across four HyperLogLog designs gives an exponent of 1.89 where the shape says 2. That is a measurement of the structures rather than of the bound — a better structure could sit lower on the same slope, and no structure of any kind can sit on a shallower one if the bound is right.

Why half-sized subsets #

The restriction to subsets of size $u/2$ looks like a technicality and is load-bearing, which is worth a paragraph because getting it wrong produces an argument that does not close.

The obvious version of the proof takes any two distinct subsets $S \ne T$ sharing a state and appends a key $x \in S \setminus T$. Then $S \cup \{x\}$ has $|S|$ distinct keys and $T \cup \{x\}$ has $|T| + 1$ — and if $|S| = |T| + 1$ those are the same number, so the two streams have the same true answer and no contradiction follows. The general argument fails.

Fixing every subset to the same size $u/2$ removes the escape: $|S| = |T| = u/2$, so the two answers are $u/2$ and $u/2 + 1$ and always differ. The cost is that the bound counts $\binom{u}{u/2}$ states rather than $2^u$, which is a discount of half a logarithm and does not change the shape.

This is the same care the sorting floor’s derivation needs and gets. $\log_2(n!)$ counts orderings rather than arrays because two arrays with the same ordering are indistinguishable to a comparison sort, and counting arrays would give a bound that is both larger and wrong. A counting argument is only as good as the set it counts.

The third kind of lower bound on this site #

There are now three, and they are worth naming together because the shapes of lower-bound arguments are not obvious from a single example.

Leaf counting. A comparison sort’s decision tree must have $n!$ leaves and a binary tree of height $h$ has at most $2^h$ of them. Counts outcomes, bounds operations. The floor under every comparison sort.

The adversary. An algorithm deciding connectivity can be watched: whatever edges it has examined, an adversary can place the answer in one it has not, so it must examine them all. Counts nothing, bounds operations, and works by playing against the algorithm rather than by counting anything. The adversary who hides the edge.

State counting. A one-pass algorithm’s memory must distinguish every input whose continuation would separate them. Counts memory states, bounds space.

The third is the one that generalises furthest, and it is the ancestor of every space lower bound in the streaming literature. The general form replaces “two subsets” with “two inputs to a two-party communication problem”, and the memory state becomes a message; the counting becomes a bound on how much has to be communicated. Everything in that literature is this argument with more machinery.

The same argument at three universes #

The floor is $\log_2\binom{u}{u/2}$ and the demonstration is an exhaustive search over subsets, so both can simply be run again at other sizes.

Moving the sweep upward is the third variation, and it is the one that says the argument is not about universes small enough to enumerate — the demonstration is, and the floor is not.

What the floor does not say #

Two things, and both are the usual caveats sharpened by the setting.

It says nothing about a particular algorithm. A structure using far more than the floor is not thereby bad, and one at the floor is not thereby good at anything else. The bitmap that achieves this floor is useless in practice for the reason the floor makes clear — it needs a bit per possible key, and real universes are 128-bit identifiers.

It says nothing about approximate answers, and that is where all the engineering is. Which is the most useful thing about it. A floor that closes off the exact problem entirely is a floor that tells everybody where to go instead, and the entire field of summaries is the answer to this one.

What is actually being spent #

One more reading of the floor is worth having, because it explains why the approximate problem is so much cheaper rather than merely stating that it is.

The exact answer has to distinguish $\binom{u}{u/2}$ inputs. The approximate answer has to distinguish only the answers that are more than $\varepsilon$ apart, and on a range from 1 to $u$ there are about $\ln u / \varepsilon$ of those. The logarithm of that is $\log\log u + \log(1/\varepsilon)$ — a handful of bits.

That is not the whole story, because the algorithm also has to be right with probability $1-\delta$ against an input it cannot see coming, and the $\varepsilon^{-2}$ in every real bound comes from that rather than from the number of distinguishable answers. But it locates the saving correctly: the exact problem is expensive because of how many inputs there are, and the approximate problem is cheap because of how few answers there are. Every summary in this phase is exploiting the second number, and the first number is what the floor counts.

There is a version of the same statement for the frequency half. Answering “how often did key $x$ occur” exactly, for arbitrary $x$, requires distinguishing every possible frequency vector and is linear in the universe by the same argument. Count-Min’s escape is the same escape: give up on the tail, be additively wrong by a share of the stream, and the requirement collapses to a few thousand bits. The floor is not a limit on what can be built; it is a statement about which question was being asked.

The floor names a universe, and it names a stream length too #

The comparison that opens the section on changing the problem — a few thousand bits against four billion — is the right order of magnitude for the question it asks and it is not the right comparison for most deployments, and the difference is a clause in the argument rather than a defect in it.

The counting argument restricts attention to subsets of size $u/2$. A stream realising one of those contains two billion distinct keys when the universe is four billion. So the four-billion-bit floor is a statement about an algorithm that must be exact on streams containing up to half the universe — and a deployment counting twenty thousand distinct visitors out of a four-billion-key identifier space is not being asked for anything of the kind.

Redo the count with the stream length in it. An algorithm exact on streams of at most $d$ distinct keys must distinguish the $\binom{u}{d}$ subsets of that size, which for $d$ far below $u$ is about

$$d\left(\log_2 \frac{u}{d} + \log_2 e\right) \text{ bits}$$

— roughly nineteen bits per distinct key at $u = 2^{32}$ and $d = 20{,}000$, so about 380,000 bits in total. That is the honest floor for that workload, it is four orders of magnitude below the headline figure, and it is still 75 times what the HyperLogLog on the same plate spends.

Which is a smaller saving and a better argument. A factor of a million invites the reading that exact counting is impossible, and it is not — 380,000 bits is 47 kilobytes, which is nothing, and any system counting twenty thousand things can simply keep them. A factor of 75 is the real trade and it is the one that decides deployments: the summary wins because it holds while the cardinality grows without anybody having sized for it, not because the exact structure could never have been afforded.

The general lesson is the one this collection keeps arriving at from different directions. A bound quoted with one of its parameters left at its worst case is a bound about a workload nobody has, and the repair is the same as everywhere else: name the parameters, all of them, and recompute. The universe size was named on every plate here from the start. The stream length was the one that was not, and it is in the floor just as firmly.

What the argument asks of the algorithm, which is very little #

One feature of this floor is worth separating out, because it makes the bound stronger than its neighbours in a way the family table does not show.

The construction appends a single key and asks once, at the end. It does not require the algorithm to answer after every arrival, it does not require the answer to be available at any intermediate point, and it does not care how much computation happens when the query comes. All it needs is that two streams reaching the same state produce the same final answer, which is true of any deterministic procedure whatever.

Compare that with the windowed floor, whose statement includes an answer after every arrival, or with the multi-pass constructions, which are about how many times the input may be read. Those bounds buy their strength partly from what they demand of the algorithm. This one demands almost nothing and still comes out linear in the number of distinct keys.

That is worth knowing when reading the family table above, because it says which floors would survive a change of setting. Relax the windowed floor’s requirement to a single query at the end and it weakens immediately — an algorithm told in advance that it will be asked once can defer. Relax this one and nothing happens, because it was never using the requirement. A bound that leans on a strong assumption is a bound to check against a deployment that may not make it, and this is the rarer kind that does not lean on anything.

Why a floor is worth having #

The site’s position on floors has been consistent across three fields and is worth restating where it applies to a resource rather than to an operation count.

A floor turns “nobody has found anything better” into “there is nothing better”, which is a different kind of statement and closes a line of enquiry. It also gives every algorithm a denominator: the gap between a structure and its floor is a number, and how close anything gets to the floor is the essay about reading it. A structure at 1.02 times the floor is finished; one at 40 times it is an invitation.

Here the exact floor is achieved to within a few per cent by the obvious algorithm, so the denominator says the exact problem is done. And that is precisely the information that sends the whole field somewhere else — into a relaxed problem whose own floor is known only up to a shape, where the structures are within a constant of that shape, and where the interesting question stops being how few bits and starts being what the bits are allowed to be wrong about.