The error of a difference

The summaries that add established what a mergeable summary is: two HyperLogLog sketches built over two streams, merged register by register, are byte for byte the sketch the concatenated stream would have produced. The union is free and it is exact — not exact in its estimate, but exact in the sense that merging introduces no error at all beyond the error the sketches already had.

From that it is one line of arithmetic to an intersection. The inclusion–exclusion principle says

$$|A \cap B| = |A| + |B| - |A \cup B|,$$

every term on the right is a cardinality, every cardinality is what these sketches estimate, and the union comes from a merge that costs nothing. So a system that holds a sketch per day can answer “how many users visited on both Monday and Tuesday” without holding the users.

It can, and the answer may be off by a factor of three.

Nothing about the sketches changed along that curve. The same three estimates, each with the same 1.6% relative error, were subtracted the same way. What changed is the size of the thing they were subtracted down to.

Where the error goes #

The mechanism is a single observation and the plate that carries it is the only one on this page that is flat.

Each of the three estimates is within about 1.6% of its own value, and the three values are all of the order of the union. So the absolute error of the subtraction is of the order of 1.6% of the union — a few thousand keys — whatever the intersection happens to be. Divide that absolute error by the intersection to get a relative error, and the divisor is the only thing moving.

That is the whole of it. Written as a rule: the relative error of an intersection estimated by inclusion–exclusion is about $\varepsilon / J$, where $\varepsilon$ is the sketch’s own relative error and $J$ the Jaccard index. At the measured $\varepsilon$ of 0.008 and $J = 0.0101$ that is 79%, which is what the first plate reads to two figures.

Two details of the flat plate are worth having. Inclusion–exclusion’s share of the union sits below the union estimate’s own error, which is not an accident: the three estimates are made from the same hash function over overlapping key sets, so their errors are correlated and the subtraction cancels part of them. And the correlation is a real help that cannot rescue anything, because a factor of two on a quantity that is already a fixed fraction of the union does not change what happens when the union is a hundred times the answer.

A number that is worse than no number #

It is worth being precise about what a 146% relative error means, because “the estimate is 146% out” can be read as though the answer were merely imprecise.

The true intersection at that point is 1,000 keys out of a union of 199,000. The estimate is a difference of three numbers each around 150,000, each carrying an absolute error of a thousand or so. Over forty seeds the estimates run from −2,753 to 7,103 with a median of 1,423, and twelve of the forty are negative — an intersection of fewer than no keys. At the next point up, a Jaccard index of 0.010, five of forty are still negative.

The implementation here reports whatever the arithmetic gives, negatives included, because clamping at zero would turn a roughly symmetric error into a biased estimate and make every plate on this page look better than the method is. A production system that clamps — and most do, since a negative count is obviously wrong — has thereby introduced a bias it does not measure, on exactly the queries where the estimate was worthless.

So the failure mode is not a loose answer. It is an answer that carries no information about the quantity at all while looking exactly like the answers that do, since nothing in the returned number says which regime it came from. That is what makes this worse than a method that simply gave up: a sketch that is allowed to be under is the page about estimators whose failures are at least visible in their sign.

The question decides the accuracy, not the sketch #

A sketch’s accuracy is usually stated as a property of the sketch. “HyperLogLog at p = 12 has a relative standard error of 1.63%” is a sentence about 20,480 bits and a hash function, and it is true, and it is not transitive.

Four times the state buys half the error, everywhere, exactly as the correction that makes it work describes — and it moves the point where the answer becomes worthless by a factor of about two and no more. A system that needs intersections at a Jaccard index of 0.01 cannot get there by making its sketches bigger: bringing 79% down to 20% takes sixteen times the state, because the error falls as the square root of the bits, and bringing it to 5% takes two hundred and fifty-six times.

This is the same shape of trap as an error measured against the answer records for rank queries, and it generalises past sketches: a stated relative error belongs to the quantity it was stated about, and a quantity derived by subtraction does not inherit it. What is inherited is the absolute error, and absolute error is only reassuring beside a large number.

Why the flat line is the honest one #

A reader who wanted to defend inclusion–exclusion could point at the share plate and say the method is performing exactly to specification: the errors of the three estimates are what they were advertised to be, they combine the way errors combine, and nothing has gone wrong. That is correct and it is the point.

The defect is not in the arithmetic; it is in the transfer of a guarantee from one quantity to another. A sketch is sold with a relative error because a relative error is what a user of a cardinality wants, and relative error is preserved by nothing — not by subtraction, not by division, not by any operation that can make the result small. The quantity that is preserved is the absolute error, and the absolute error was never the headline because on its own it says nothing: a thousand keys is a triumph against a union of two hundred thousand and a catastrophe against an intersection of a thousand.

So the flat plate is the one to carry away. It says the sketches did their job, and it says why doing their job was not enough.

Sampling instead of subtracting #

There is a method that does not subtract, and it is already on the plates above.

Keep the $k$ smallest hash values of each set. The $k$ smallest of the union are the $k$ smallest of the two sets taken together — which is why these merge exactly, the property the summaries that add measured — and those $k$ hashes are a uniform random sample of the union, since the hash function orders the keys independently of everything else about them. Count how many of them belong to both sets. That share is an estimate of the Jaccard index directly, and multiplying it by an estimate of the union gives the intersection.

The estimate is a binomial proportion out of $k$ draws, so its error depends on how many of the $k$ sampled keys land in the intersection, and that falls with the overlap too — but it falls as a square root rather than as a reciprocal, which is a different curve entirely. At a Jaccard index of 0.005 the minimum values are 18.4% out where inclusion–exclusion is 146%.

That comparison is not fair, and the unfair part is the interesting part.

At equal state neither method wins. Above a Jaccard index of about 0.05 the subtraction is two to three times more accurate, because HyperLogLog spends five bits on a register where the minimum values spend thirty-two on a hash, and at equal bits that is six times as many of them. Below it the subtraction collapses and the sample does not.

So the choice is not between a good method and a bad one. It is between a method whose error is a fixed share of the union and one whose error is a share of the answer, and which of those is preferable is decided entirely by how large the answer is relative to the union — which is the thing the query is about and is not known before the query is run.

Spending more bits widens the range in which sampling is the better method, which is the opposite of what a reader would guess. Both errors fall as the square root of the bits, so a plain scaling argument says the crossing should not move at all. It moves because the two errors are not the same kind of quantity: inclusion–exclusion’s is a fixed share of the union and is divided by $J$, while the sample’s is a binomial proportion over $k$ draws and behaves as $\sqrt{(1-J)/kJ}$ — which falls faster in $J$ than $1/J$ does. Doubling the accuracy of both moves the point where the first curve overtakes the second up rather than leaving it in place.

The practical reading is the useful one. A system that plans to hold large sketches should not assume it is buying accuracy on intersections; past a point it is buying a wider band in which it should be using a different estimator entirely.

The set size moves it too #

Smaller sets make inclusion–exclusion worse at every overlap, and the reason is not that the sketches are less accurate — a HyperLogLog’s relative error does not depend on the cardinality across this range, which is what a count read off the leading zeros establishes once the small-range correction is past. It is that the intersections themselves are small in absolute terms: at a Jaccard index of 0.005 there are a hundred keys in common, and 0.8% of a union of twenty thousand is a hundred and sixty. The estimate is being asked to resolve a quantity smaller than its own error bar.

The minimum values get slightly better on the smaller sets, because $k = 4{,}096$ hashes out of a union of 19,900 keys is a fifth of the whole union rather than a fiftieth — the sample stops being a sample. That is a corner worth naming rather than a general property: when $k$ approaches the union’s size the method is holding most of the data and the error is not sampling error any more.

What a system can actually do #

The honest reading of the crossing is that an intersection cannot be answered well by a single summary chosen in advance, and there are three responses.

Hold both. Forty thousand bits a day instead of twenty, and answer each query with whichever method suits the overlap it turns out to have. The overlap is estimated by the minimum values, cheaply and before anything is subtracted, so the choice can be made at query time from the data rather than guessed at write time — and the crossing is where to switch, which is a number the system can measure for its own shapes rather than take from here.

Report the error bar rather than the estimate. The rule $\varepsilon / J$ is computable once $J$ is estimated, so a system that subtracts can say how far out the answer is likely to be — and a 146% error bar is a useful answer where a wrong number is not. That is the same discipline a summary’s silence is a bound, not a count asks for one structure over.

Or refuse the query. An intersection at a Jaccard index of 0.005 over sketches of this size is not an approximate answer; it is noise with a number printed on it. The sketches were the right structure for the question they were built for, and a question that arrives later is not obliged to be answerable from them — which is what the floor under a summary says in its strongest form, with a counting argument rather than a measurement.

What is measured and what is assumed #

The sets are the same size and the keys are disjoint outside the overlap. That makes the Jaccard index a single parameter and it is the cleanest case. Two sets of very different sizes behave worse: the union is then dominated by the larger, so the absolute error is a fraction of the larger set while the intersection can be at most the size of the smaller, and the ratio can be bad at Jaccard indices where these plates are still comfortable.

Every point is an average over sixteen seeds and the error is an absolute deviation, not a standard error. The quantity plotted is the mean of $|\hat{I} - I| / I$ across seeds, which is a mean absolute relative deviation. It is the number a reader wants — how far out was it — and it is not the standard error a sketch’s documentation quotes, which is about half as large for a symmetric estimator.

The truth is a hash map. Every intersection, union and Jaccard index on this page is computed exactly over the key sets by a structure that shares nothing with the sketches, which is the rule for every plate in this field. An estimate compared against another estimate would draw a convincing curve about nothing.

The merge is exact and is not where anything goes wrong. Every union here comes from merging two sketches register by register, and that operation introduces no error whatever — the merged sketch is identical to one built over the concatenated stream, which is the property the state a merge is standing in for examines in the cases where it fails. The whole of this page’s difficulty is downstream of a merge that behaved perfectly.

Nothing here is timed, and the state figures are the registers alone: 20,480 bits is $2^{12}$ registers of five bits, and it excludes the hash function, the object header and the three-sketch working set a real query holds.

And inclusion–exclusion over more than two sets is worse, by an amount this page did not measure. Three sets need seven terms, four need fifteen, and each term carries its own share of a union — so the absolute error grows with the number of terms while the answer shrinks. The rule $\varepsilon / J$ becomes something like $\varepsilon \sqrt{2^d} / J$ for $d$ sets if the errors are independent, and they are not independent here, which is why the page stops at naming the shape.

Still open: the sample that is kept for the question #

The minimum values win below the crossing because they sample the union and then ask about the sample. That suggests a structure this page has not built: keep the $k$ smallest hashes and a HyperLogLog, spend the extra bits, and use each where it is better.

The interesting part is not the combination but what it would cost to size. The crossing sits at a Jaccard index of about 0.05 at twenty thousand bits and about 0.11 at eighty thousand, and it must move with the ratio of the two set sizes as well — so a system choosing a split of its bit budget is choosing where that crossing falls, and it is choosing it before it knows which queries will arrive.

The measurement that follows sweeps the split between the two structures at a fixed total state, locates the crossing for each split, and asks whether there is a division whose worse method is never much worse than the better one — a minimax split rather than a tuned one. The prediction from the shapes here is that there is, and that it is nowhere near even, since the subtraction is three times better over most of the range and catastrophically worse over a little of it, and a rule that protects against the catastrophe should buy that protection cheaply.