A budget split before the question arrives

The error of a difference ended on a structure it had not built. Two ways of estimating an intersection from sketches cross: subtracting HyperLogLog estimates by inclusion–exclusion is better when two sets overlap heavily, and sampling the union through its $k$ smallest hashes is better when they barely overlap. The crossing sits at a Jaccard index of about 0.05 at twenty thousand bits a sketch, and it moves when more bits are spent. So a system could keep both structures and answer each query with whichever suits it.

The part that essay flagged as the interesting one is the sizing. A system that holds a sketch per day, per region or per campaign decides how many bits go to each structure when the sketch is built. The questions come later: which two days, which two regions, and how much those sets turn out to share. The split is fixed before the overlap is known, and the overlap is what decides which structure was worth having.

That essay predicted the answer. There should be a split whose worse case is never much worse than the better method would have been — a minimax split rather than a tuned one — and it should be nowhere near even, because the subtraction is better over most of the range and catastrophically worse over a small part of it, so protecting against the catastrophe ought to be cheap.

Both halves of that prediction are measured below. The first holds. The second does not, and the reason it fails turns out to matter less than a problem the prediction never mentioned: choosing between the two estimates once the query has arrived. That choice has a textbook rule, and the rule is wrong on every draw.

One budget, nine ways to spend it #

The budget is 40,960 bits a set, the figure the earlier essay named when it suggested holding both. It is split in eighths. The HyperLogLog gets $f \times 8{,}192$ five-bit registers and the sample gets $(1-f) \times 1{,}280$ thirty-two-bit hashes. At $f = 0$ the whole budget is a sample of the 1,280 smallest hashes. At $f = 1$ it is a HyperLogLog of 8,192 registers. At $f = \tfrac12$ it is 4,096 registers beside 640 hashes, twenty thousand bits each, which is exactly the pair the earlier page compared.

A HyperLogLog of 1,024 or 7,168 registers is not a power of two, so the one measured here picks its register from the high part of the hash multiplied by the register count, and reads the rank from a second hash. That is a different layout from the power-of-two sketch the earlier essays used. It is checked rather than assumed: at 4,096 registers over forty seeds its relative error is 1.85%, against the analysis’s $1.04/\sqrt{m} = 1.63\%$. That is about an eighth worse than the textbook figure. The difference is recorded here because every error on this page inherits it.

Each split can give two estimates of $|A \cap B|$:

• the subtraction, $\hat{|A|} + \hat{|B|} - \widehat{|A \cup B|}$, all three read from HyperLogLogs, the union from a register-wise merge that loses nothing;
• the sample, the share of the union’s $k$ smallest hashes that are present in both sets, multiplied by an estimate of the union. When the split holds a HyperLogLog, the union estimate comes from it, since it is the more accurate of the two per bit. The pure sample has to use its own.

The sets are two of 100,000 keys each. Their Jaccard index runs over ten values from 0.98 down to 0.001, and every point is 64 seeds against the exact intersection. The error reported is the mean absolute relative deviation, the convention the earlier essay used and stated: how far out the estimate was, as a share of the true answer. That denominator is a choice, and an error measured against the answer is the page on what it hides.

The yardstick is an oracle. At each overlap it takes the best mean error that any of the nine splits achieved with either estimate. That is what a system would get if it knew the overlap before deciding how to spend its bits, which no system does. A split’s regret at an overlap is its error divided by the oracle’s, and its worst regret is the largest of those across the range. The split with the smallest worst regret is the minimax split.

A half that is never far from the best #

Each pure structure is the oracle at its own end of the range and far from it at the other. All HyperLogLog is the best possible at every overlap down to a third, and 12.8 times the best at a Jaccard index of 0.001, where it reports 832% error on an intersection of a hundred keys. All sample is the best possible from 0.1 downwards, and 2.7 times the best at 0.82, where it cannot match what 8,192 registers do for a union-sized answer.

The even split is never the best possible anywhere. It is never far from it either. At the high end it reads 1.2% against the oracle’s 0.8%, and at the low end 101.5% against 64.9%. Its worst point is in the middle, at a Jaccard index of a third, where it reads 2.7% against 1.5%. That ratio, 1.81, is its worst regret over the whole range.

So the first half of the prediction holds. A split exists whose worst case beats both pure structures, and by a wide margin: 1.81 against 2.66 and 12.83. The second half does not hold. The minimax split is the even one, with five eighths a hair behind at 1.88, and the curve across the middle is shallow enough that five and six eighths are within a fifth of it and three eighths within a third. “Nowhere near even” was the wrong shape.

The reason is that neither end is cheap to protect. Halving a structure’s bits costs it about $\sqrt{2}$ in accuracy, because a HyperLogLog’s error and a sample’s both fall as the square root of what they hold — the law the correction that makes it work measured for the registers and a count read off the leading zeros derived from the averaging. A split that gives most of the budget to the HyperLogLog keeps the high end nearly at its best and starves the sample. The sample is the only thing standing between the low end and the subtraction’s collapse, so a starved sample pays in full there. At seven eighths the sample holds 160 hashes and the worst regret is 2.95, set at a Jaccard index of 0.0025. Protection against the catastrophe was never going to be cheap, because the thing doing the protecting has to be large enough to work.

And 1.81 is not a cheap premium either. Read at the overlap where it is paid, it means a query about two sets sharing a third of their keys is 2.7% out rather than 1.5%. A system that knew all its queries would sit at such overlaps would not have paid it. The minimax split is insurance, and like the insurance what a planner pays to find out what to pay priced, it is bought with accuracy on the cases that turn out not to need it.

The textbook rule chooses wrongly every time #

The minimax plate has three lines, and the gap between them is larger than any gap between splits. Holding both structures is only half of a design. The other half is deciding, when a query arrives, which of the two estimates to report.

The obvious rule uses the analysis. Each estimate carries a textbook variance that can be computed from quantities the query already has. For the subtraction, three estimates each with relative error $1.04/\sqrt{m}$ are combined, so the variance is $\varepsilon^2(|A|^2 + |B|^2 + |A \cup B|^2)$ with the estimated sizes plugged in. For the sample, a binomial share of $k$ draws is carried by the union estimate, giving $(J \cdot |A \cup B|)^2 \left(\frac{1-J}{kJ} + \varepsilon^2\right)$ at the estimated Jaccard index. The rule reports whichever estimate has the smaller predicted variance. It uses nothing a running system lacks, and it is what a careful implementation would write first.

At the even split it does worse than holding the sample alone. Its worst regret is 2.93, against 2.66 for spending all forty thousand bits on the sample and never building a HyperLogLog at all.

The audit shows why. The formula for the sample is right: its predicted error sits on its measured one at every overlap except the smallest, where a hundred shared keys make the binomial approximation loose. The formula for the subtraction is wrong, and always in the same direction. It predicts nearly twice the measured error at high overlap and about a third more at low overlap. Believing it, the rule concludes on every one of 640 draws, across all ten overlaps, that the sample is the better estimate. It is not a rule that sometimes chooses badly. It is a constant, and the constant is the sample at half size.

The formula is wrong because it treats the three errors as independent, and they are not. The earlier essay noticed the symptom without chasing it: the subtraction’s error as a share of the union sat below the union estimate’s own error. The three HyperLogLogs hash the same keys with the same function. A register that happens to run high for $A$ runs high for the union, because the union’s register is the maximum of $A$’s and $B$’s. When $\hat{|A|}$ is too large, $\widehat{|A \cup B|}$ tends to be too large with it, and the subtraction cancels part of the excess. The variance of a difference of correlated quantities is the sum of their variances minus twice their covariance, and the textbook formula drops the covariance.

That is a general hazard with a specific shape here. Every piece of the rule is a correct statement about one sketch — the relative error of a HyperLogLog is $1.04/\sqrt{m}$ — and the combination is wrong because the sketches are not independent draws. It is the same trap the summaries that add set out from the other side. Mergeability is valuable precisely because the sketches share a hash function, and sharing a hash function is precisely what makes their errors move together.

The weighting rule fails in the same way and more gently. It averages the two estimates with weights inversely proportional to their predicted variances, so an overstated variance for the subtraction gives the subtraction too little weight instead of none. At the even split that is a worst regret of 2.04. It is better than the switch and still worse than a rule that does not use the formula at all.

A crossing measured once, before any query #

The rule that works throws the subtraction’s formula away. For each split, the overlap at which the two estimates cross is located once, on 32 calibration seeds that the measurement never sees, by interpolating between the sweep points on either side. At query time the sample’s own estimate of the Jaccard index is compared with that crossing: above it, report the subtraction; below it, report the sample.

That rule uses the one prediction that was right — the sample’s estimate of $J$, which is a proportion and is well behaved — and replaces the one that was wrong with a measurement. On the minimax plate it sits on the curve a rule would trace if it knew the overlap exactly, split for split. At the even split the two are identical at 1.81. The rule loses nothing by having to estimate $J$, because the crossing is at 0.09 and at that overlap the sample’s estimate of $J$ is good to a few per cent. A draw near the crossing that lands on the wrong side chooses between two estimates of nearly equal error, so it costs almost nothing.

The crossing is not a property of the two estimators. It is a property of the split. Give the HyperLogLog more of the budget and it stays better down to smaller overlaps, while the sample shrinks and needs a smaller overlap still before it wins. At two eighths the crossing is 0.17; at seven eighths it is 0.016, ten times lower. At one eighth the HyperLogLog has 1,024 registers and the subtraction never wins at all, even at a Jaccard index of 0.98. Its estimates of the three sizes are each three to four per cent out, and the sample’s 1,120 hashes do better on every query.

This is why the rule has to be stored with the sketch. The earlier essay located the crossing at about 0.05 for twenty thousand bits each. Here the even split’s crossing is 0.093, and most of the difference is the HyperLogLog: the layout measured here is an eighth less accurate than the power-of-two one, which makes the subtraction worse and moves the crossing up. The sample borrowing the HyperLogLog’s union estimate moves it a little further — at a Jaccard index of 0.053 the sample is 10.5% out with the borrowed union and 12.6% with its own. Neither change is large, and together they nearly double the threshold. A threshold carried over from one design to another is a threshold for a structure that is not the one running. It is the same failure as a constant copied between libraries: a number stated without the configuration it was measured on.

Two things about the calibration are worth stating. It is the same move a planner that knows how sure it is made with a confidence bound: replace a quantity the formula gets wrong with one measured on data the decision will not be scored on. It uses the truth, on seeds set apart for it, which is what a system can do for its own data offline by building sketches over pairs of sets it can also count exactly. And it is 32 seeds, located by interpolation over a sweep that samples the overlap coarsely. Its precision is visible in the plate: three and two eighths land within a hundredth of each other, which the sizes alone cannot explain and which is noise. The measured rule does not need the crossing to be precise. It needs it to be on the right side of the shallow minimum, and it is.

What the split depends on is the question range #

The minimax was taken over overlaps from 0.98 down to 0.001. That lower end is a choice, and it is the choice that sets the answer.

A system whose queries never ask about two sets sharing less than a tenth of their union should spend nothing on the sample. All HyperLogLog is within 8% of the best possible across that whole range, and any sample would be bits taken from the structure that answers every one of those queries best. The first overlap below a tenth changes that at once. Down to 0.053 the minimax split is seven eighths and its worst regret jumps to 1.56, because the subtraction at 7,168 registers is already 15% out there and the oracle’s sample is at 9.5%.

From 0.026 down, the minimax split settles at five eighths and the worst regret grows only slowly, from 1.75 to 1.81. The low end costs a sample of a few hundred hashes to cover. Once that sample exists, covering still smaller overlaps costs very little more, because the sample’s error grows as $1/\sqrt{J}$ while the subtraction’s grows as $1/J$. Past a point the sample is the only estimate in play and its regret is set by how much of the budget it got.

So the question the budget has to answer before any query arrives is not which overlaps are likely. It is which overlaps must be answerable, and the answer comes in two regimes. A system that can promise every query overlaps by a tenth builds one structure. A system that cannot builds two, in a proportion between a half and seven eighths that matters less than the decision to build both, and pays about 1.8 times the best possible error somewhere as the price of not knowing. Whichever it builds, the per-query error can be reported with the estimate rather than left implicit — the discipline a summary’s silence is a bound, not a count asks for in a different structure. The step between the two regimes is sharp. The smallest overlap a system must answer is worth finding out before the sketch is built, and it is rarely written down.

When one set is ten times the other #

Everything above uses two sets of the same size. The earlier essay said sets of different sizes would behave worse and did not measure it.

When one set is ten times the other, the Jaccard index cannot exceed 0.1, so the whole range sits in the region where the equal-sized study said the sample should win. It does not win by as much as that suggests. The sample of the union is now nine-tenths keys of the larger set, and the share present in both is at most one draw in eleven. Asking a sample of 1,280 hashes about the smaller set wastes most of it on keys that could never have been in the intersection. At the top of the uneven range the pure sample is 7.31 times the best possible. The bad end has swapped: for equal sets the sample was the safe structure and the HyperLogLog the dangerous one, and for sets ten times apart it is the other way round.

The minimax split does not move much. It is five eighths at 1.85, with three eighths at 1.97 and the even split at 2.36. That last figure sits above both its neighbours, a jag that the sizes cannot produce and 64 seeds do not resolve. The durable result is that the split which protects against both ends is still in the middle and still costs less than a factor of two. What moves is which end is expensive, which is the thing a system designer would most want to know and could least guess.

The textbook switch gets much worse. On the uneven pair its formula overstates the subtraction’s error by 2.7 to 9 times rather than 1.3 to 2, which fits the mechanism: the union is dominated by the larger set, so $\widehat{|A \cup B|}$ and $\hat{|A|}$ are nearly the same estimate and their errors nearly cancel in the subtraction. The switch again chooses the sample on every draw, and at the top of the range that sample is 11 times the best possible at the even split and 13 at five eighths. The measured crossing moves down with the size ratio (the second line on the crossings plate) and keeps the split at 1.85. A rule that is calibrated survives a change of workload that a formula does not, because a calibration can be redone and a formula’s missing term stays missing.

What was measured and what was not #

Every error is against the exact intersection, counted by a hash set that shares nothing with the sketches. The oracle is the best of eighteen noisy means at each overlap, and a minimum of noisy values is biased low, so every regret on this page is slightly overstated. At 64 seeds the mean absolute deviation has a standard error of about a tenth of itself. That is enough to trust the ordering between the ends and the middle and not enough to rank three eighths against five — the situation a result the size of its own noise is about, where a difference smaller than its own spread is reported as a difference.

The budget is fixed at 40,960 bits a set. At four times the budget both structures’ errors fall by half and the crossings move, as the earlier essay found for the pure structures. Whether the minimax split stays at a half is predicted by the square-root scaling, which halves both sides alike, and was not measured.

The HyperLogLog is not the textbook one. Its register is chosen by a multiply-high so that any register count works, and at 4,096 registers its measured error is 1.85% against the analysis’s 1.63%. That handicaps the HyperLogLog side by about an eighth on every plate. The direction of every conclusion survives a correction of that size, and the precise location of the minimum might not.

Only two estimates are compared. A sample of the union can estimate $|A|$ and $|B|$ as well, and a HyperLogLog’s registers can be compared position by position to estimate the overlap directly — the approach behind several published intersection estimators. Neither is measured here. Each would add a third estimate and a third crossing without changing the question the page asks: whether a budget fixed in advance can be split so that no question costs much more than it would have with the answer known.

No split beats the floor. Any exact intersection needs state that grows with the sets, which is what the floor under a summary proves for the cardinality alone; every error on this page is the price of staying far under it.

Nothing here is timed. The sample’s query cost is a merge of two sorted lists of up to 1,280 values and the HyperLogLog’s is a pass over its registers. Both are negligible beside the bits, which are the resource this page prices.

Still open: the covariance, estimated rather than dropped #

The textbook rule failed because its variance for the subtraction omitted a covariance. The measured crossing repaired that by not using the formula at all. There is a third option this page did not try: keep the formula and estimate the covariance.

It is estimable. The three HyperLogLogs share their registers position by position, so the registers where $A$ and the union agree, and the registers where the merge took $B$’s value, are both visible. How often the union’s register equals $A$’s is itself a statistic about the overlap. A variance for the subtraction that includes the covariance read from those agreements would make the per-draw switch honest, and it would have one advantage over a calibrated threshold: it needs no calibration seeds and cannot go stale when the workload changes.

The measurement that follows computes that covariance from the registers, puts it into the switch and the weighting rule, and asks whether either reaches the measured crossing’s 1.81 at the even split. It also asks whether either survives the ten-to-one pair better, where the correlation is strongest. The prediction is that the weighting rule, once its weights are right, should beat the threshold. It is choosing a mixture where the threshold chooses a side, and on the shallow ground near the crossing a mixture of two estimates with comparable errors is better than either. If it does not beat the threshold, the covariance read from registers is too noisy to use per query, and the calibration was doing work no formula can.