The covariance the registers already hold

A budget split before the question arrives divided 40,960 bits a set between a HyperLogLog and a sample of the smallest hashes, so that an intersection could be estimated either by subtracting cardinalities or by reading the sample’s share of the union. The split that was never far from the best was the even one, a worst regret of 1.81 against an oracle that knew the overlap. But that held only for one rule for choosing between the two estimates, and the obvious rule failed completely. The textbook variance of the subtraction $\hat{|A|} + \hat{|B|} - \widehat{|A \cup B|}$ treats its three errors as independent, overstated the subtraction’s error by up to twice, and chose the sample on all 640 draws. Weighting the two estimates by those variances did better, 2.04, and still lost to a rule that ignored the formula entirely: a crossing located once on calibration seeds, compared at query time with the sample’s estimate of the overlap.

The closing section named a third option. The formula failed because it dropped a covariance, and the covariance is visible. The three sketches index their registers identically, register by register, so how A’s registers and the union’s agree is a statistic the query already holds. It proposed estimating the covariance from the registers, putting it into both the switch and the weighting, and predicted that the weighting rule, once its weights were right, would beat the calibrated threshold. A threshold chooses a side, and near the crossing a mixture of two estimates with comparable errors is better than either. If the weighting did not win, the covariance read from registers was too noisy to use per query, and the calibration was doing work no formula could.

The weighting wins, and the margin is largest exactly where the calibration had to be redone.

Reading a variance from the sketch itself #

The covariance does not need a formula of its own. The variance of the whole subtraction can be read directly, with the covariance inside it, by cutting the sketch into pieces that each estimate the same thing.

Cut the $m$ registers into 32 contiguous groups. A group is a HyperLogLog of $m/32$ registers over the keys that happen to hash into it, each register still holding the longest run of leading zeros its keys produced, the evidence a count read off the leading zeros turned into a count. Thirty-two times a group’s estimate is an estimate of the whole cardinality. That holds for A’s registers, for B’s and for the union’s, and because the three share their indexing, group $g$ of the union is exactly the register-wise maximum of group $g$ of A and of B. So each group gives a whole subtraction from its own registers, and the 32 subtractions vary from group to group the way the full subtraction varies from sketch to sketch. Their spread, divided by 32, estimates the variance of the full subtraction, the method of batch means applied to a sketch’s own registers. A group in which A’s registers ran high is a group in which the union’s ran high too, and the cancellation the textbook formula missed is in every group’s subtraction already.

Nothing is calibrated and nothing about the truth is used. The query reads its own registers twice: once for the three estimates, once in groups for their spread. The sample’s variance stays the binomial one the earlier essay found right, the share of $k$ draws carried by the union estimate. Two rules use the register variance. The switch reports whichever estimate has the smaller variance; the weighting averages them with weights inversely proportional to their variances. Everything else is the earlier study’s own: the same sets, the same 64 seeds at each of ten overlaps from a Jaccard index of 0.98 to 0.001, the same oracle, the same worst regret. A check confirms that the register pass reproduces the study’s subtraction on every draw.

The switch matches the crossing, the weighting beats it #

At the even split, the switch on the register variance has a worst regret of 1.81, exactly the measured crossing’s, and the weighting on it has 1.70 — the best of any rule at any split, and below the 1.81 that choosing the better estimate with the overlap known achieves. The prediction’s reasoning holds. Given variances that are right, choosing per draw does as well as a threshold located in advance, because the threshold was only ever a proxy for the comparison of two variances. And a mixture of the two estimates does better than any choice between them, including the choice made with the answer in hand.

The register rules also make the split curve shallower. The weighting’s worst regret is 1.85 at three eighths, 1.70 at four and 1.83 at five, where the threshold’s was 2.31, 1.81 and 1.88. The middle of the budget is a wider valley than it was, so the exact split matters less. The two ends of the curve need care. At one eighth the HyperLogLog holds 1,024 registers, its groups hold 32 each, and the register variance is coarse; the weighting is 3.53 there, slightly better than every other rule. At seven eighths the sample holds 160 hashes, and the weighting is worst of all at 4.46. That failure is the sample’s variance, not the registers’: at a Jaccard index of 0.001 a sample of 160 expects a sixth of a shared hash, its estimate of the overlap is usually nought, and a binomial variance evaluated at an estimate of nought says the sample is far more certain than it is.

How close the registers come #

Where the sets overlap heavily the registers predict the subtraction’s error to within a few per cent, 3.2% against a measured 3.3% at a Jaccard index of a third, where the textbook formula says 6.7%; where they barely overlap the registers read about a fifth low, 22.2% against 26.5% at 0.053. The textbook formula errs high everywhere, by 1.3 to 2 times. The register reading errs low at small overlaps by about a fifth, and at large overlaps it does not err at all.

Neither error is a matter of the covariance any more. A group of 128 registers is a coarse HyperLogLog, its estimates of A, B and the union are each about nine per cent out, and a subtraction of three such estimates is a much more nonlinear quantity than the full sketch’s. The harmonic mean that the correction that makes it work found worth 30% of a sketch’s error is a nonlinear average of its registers, and a small group’s average is further from linear than a large one’s. The groups’ spread therefore scales with the full sketch’s error only approximately. Where the intersection is small against the union, the subtraction is a small difference of large numbers. The spread of 32 small differences understates the spread of the large one by roughly the fifth the plate shows. The direction matters for the rules: an underestimate makes the subtraction look slightly better than it is at small overlaps, exactly where the sample should win.

It does not cost the rules much, for a reason the next plate shows. By the overlaps where the registers read low, the subtraction is so much worse than the sample that a fifth either way does not change which one wins.

The covariance the textbook drops #

Across the groups, A’s estimate and the union’s move together with a correlation of 0.99 when the sets nearly coincide and about 0.47 when they barely overlap. That is the covariance the textbook formula sets to nought. At high overlap the union is nearly A, its registers are nearly A’s registers, and the two estimates are nearly the same number, so their errors cancel almost entirely in the subtraction. At low overlap the union is A and B in equal parts, each register of the union is the larger of two nearly independent registers, and the correlation settles at about one half. There is still enough cancellation to matter, which is why the textbook formula overstates the error even there.

The switch’s choices follow the overlap the way the measured crossing did, with no crossing given to it. Between a Jaccard index of 0.82 and a third it reports the subtraction on every draw. At 0.11, near the crossing the calibration located at 0.09, it reports the subtraction on 83%, then 8% at 0.053, and none below. At 0.98 it reports the sample on 28% of draws, because at that overlap the two estimates are equally good, 1.2% each, and either choice is right. The textbook rule chose the sample on every draw at every overlap. The difference between the two switches is the covariance, read rather than assumed.

Where the mixture earns its margin #

At a Jaccard index of 0.11, where the two estimates are about equally good, the register weighting is 0.97 times the oracle’s error: better than the best any split achieved with either estimate alone, where the measured crossing is 1.57 times it. This is the prediction’s mechanism, measured. Two estimates with comparable, partly independent errors average to something better than either, and an oracle that only chooses cannot reach it. At 0.053 the weighting is 1.20 times the oracle against the crossing’s 1.47, and at 0.010 it is 1.28 against 1.44.

Away from the crossing the mixture has nothing to mix. At high overlap the sample’s weight is small and the weighting is the subtraction. At the very smallest overlap, 0.001, the subtraction’s weight is small and the weighting is the sample, a hair worse than the sample alone, because the register variance’s fifth too low lets a little of a 1,500% error leak in. The worst regret of 1.70 is set at a third, where the subtraction is the right answer and the mixture can only shade it. The gain at the crossing is larger than the gain at the worst point, and a worst-regret measure reports only the second.

When one set is ten times the other #

When one set is ten times the other, the register weighting’s worst regret is 1.42 at three eighths, against 1.85 for the measured crossing at its best split; the textbook weighting at three eighths is 7.77. The earlier essay found that the textbook formula grows far worse on uneven sets, overstating the subtraction’s error by up to nine times, because the union is nearly the larger set and its errors cancel nearly completely against that set’s. The registers see that cancellation directly. Every group’s union is nearly its group of A, the correlation between them is close to one, and the spread of the groups’ subtractions is small, as the true error is.

The crossing had to be measured again for this pair, on its own calibration seeds, to get to 1.85. In a running system those seeds are pairs of sets counted exactly offline, and what a planner pays to find out what to pay priced that kind of learning: every calibration is paid for in executed work, and paid again when the workload moves. The register rules were given nothing new. They read the same registers the same way and adapted to the change of workload because the change is in the registers. A planner that knows how sure it is found that a spread fitted to a small calibration sample is biased low and must be insured against. A variance read from the query’s own sketch needs no sample, and therefore no insurance against a sample that is out of date.

The best split moves as well. With the register weighting the uneven pair is best served at three eighths, the equal pair at four. Under the measured crossing the two were five eighths and four. The register rules recover more from a smaller HyperLogLog, plausibly because they no longer waste it: a subtraction that is used in a mixture whenever its error is comparable contributes something at overlaps where the threshold would have discarded it.

What the prediction got right #

The closing section predicted that the weighting rule, once its weights were right, would beat the threshold. At the even split it does, 1.70 against 1.81, and on the uneven pair by more, 1.42 against 1.85. It predicted the mechanism: a mixture beats a choice on the shallow ground near the crossing, where the two estimates have comparable errors. At the crossing the mixture beats the oracle that chooses. And it asked whether either rule would survive the ten-to-one pair better, where the correlation is strongest. Both register rules do, and the weighting most.

What it did not anticipate was that the switch would match the threshold exactly, not approximately, at the even split. The crossing and the register switch arrive at the same worst regret to the third decimal place, and they choose alike at every overlap but those beside the crossing. The measured crossing was a summary, located in advance, of a comparison the registers can make per query. The calibration was not doing work no formula could. It was doing the work of a formula that had been written with one term missing.

There is a general rule underneath this, and the summaries that add stated half of it. Sketches that share a hash function merge, because their registers line up, and that alignment is what makes their errors move together and a formula treating them as independent wrong. The same alignment makes the dependence measurable. Any estimate built from several aligned sketches can carry its own variance, read from groups of their registers. The error of a difference showed the subtraction’s error growing without bound as the overlap falls, and the honest response to that is not a better formula but a measured one, reported with the estimate.

What the reading assumes #

Thirty-two groups. At 4,096 registers a group has 128, coarse but usable; at the smallest split’s 1,024, a group has 32, and the register variance there is noisy. No other count of groups was run. Fewer groups would make each a better sketch and their spread a noisier statistic, and more groups the reverse.

A sample’s variance taken at face value. The binomial variance is evaluated at the sample’s own estimate of the overlap. When that estimate is nought, which at seven eighths and the smallest overlap it usually is, the variance says the sample is exact, and the weighting trusts it. This is the cause of the 4.46 at seven eighths, and it is a property of the sample’s variance, not of the registers.

One measure of error. Every error is the mean absolute deviation from the true intersection as a share of it, the earlier study’s convention. An error measured against the answer is the reminder that a denominator is a choice, and this one makes small intersections loud.

The same seeds. Every comparison is on the earlier study’s 64 seeds at each overlap. The register rules use no other draws; the measured crossing used 32 calibration seeds that the comparison never sees. The oracle and the regrets are the earlier study’s, so the numbers for the old rules reproduce its plates exactly.

Still open: a sample’s variance when it has seen almost nothing #

The weighting fails in one corner: a sample of 160 hashes asked about two sets sharing one key in a thousand. It expects a sixth of a shared hash, usually sees none, and its estimated overlap of nought makes its binomial variance nought too, so the weighting believes the sample completely at the one overlap where it knows least. The same corner made the threshold and the textbook rules choose the sample there too, but they had nothing better to choose.

The measurement that follows replaces the plug-in binomial variance with one that cannot collapse. The share is estimated with half a shared hash added to its count and its variance taken at that estimate, the correction a proportion with no successes needs, and both register rules are run again at every split on both pairs of sets. The prediction is that the weighting’s worst regret at seven eighths falls from 4.46 to under 2.5, while the even split stays at 1.70, since its sample of 640 hashes rarely sees nothing. That would leave a regret curve under two from two eighths to seven. The question is whether the last place a formula’s variance misleads a mixture is the place where an estimate has seen nothing at all, and whether a variance that admits ignorance is all a sample needs to be weighed honestly.