Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Inclusion exclusion — where it appears

Counting the elements of a union or intersection by adding and subtracting the sizes of the sets and their overlaps. Applied to estimates it is exact in form and fragile in practice, because each term's error is a share of a large number and the answer may be small.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

Also named here as jaccard index — the same set of essays touches all of them, so they are one junction rather than several.

0.010.10.11Jaccard index of the two setsrelative error of the intersectionas wrong as the answerinclusion–exclusionthe minimum valuesHyperLogLog p = 12, 20,480 bits · bottom-4,096, 131,072 bitstruth from a hash map over 200,000 keys

The error of a difference

Three sketches, each within a per cent or two of its own answer, subtracted into an intersection. At a Jaccard index of 0.82 the answer is 1.3% out. At 0.005 it is 146% out — the same three sketches, the same accuracy, a different question. The error never grew: it stayed a fixed fraction of the union, and the union stopped being the thing being asked about.

streaming · Cardinality 01/82/83/84/85/86/87/811×1.5×2×3×5×10×share of the bits given to the HyperLogLogworst error over all overlaps ÷ the best possible1.81×switch at a crossingmeasured in advanceswitch on the textbookvariancesweight by the textbookvariances40,960 bits a set, 64 seeds, J from 0.98 to 0.001ringed: the minimax split

A budget split before the question arrives

Forty thousand bits a set, divided between a HyperLogLog and a sample of the smallest hashes before anyone knows which intersections will be asked for. Given all to either structure, the worst query is 2.7 or 12.8 times as far out as the best possible. Split in half, it is 1.8 — but only if the choice between the two estimates is made from a crossing measured in advance. The textbook error formulas make the choice wrongly on every one of 640 draws.

streaming · Cardinality 01/82/83/84/85/86/87/812×3×5×10×share of the budget given to the HyperLogLogworst regretswitch, textbook varianceweight, textbook varianceswitch at a measuredcrossingswitch, variance fromregistersweight, variance fromregisterstwo sets of 100,00032 groups of registers

The covariance the registers already hold

A budget split between a HyperLogLog and a sample of the smallest hashes chose its intersection estimate wrongly on every draw, because the textbook variance for a subtraction of three sketches drops their covariance. A crossing measured on calibration seeds repaired the choice at a worst regret of 1.81. Read instead from the registers themselves — thirty-two groups of them, each a small sketch of both sets and their union — the variance makes the per-draw switch match the crossing exactly, and makes the weighted mixture the best rule measured: 1.70 at the even split, and 1.42 against 1.85 when one set is ten times the other, with no calibration at all.

streaming · Cardinality 123451234567eighths of the budget in registersworst regret over every overlapregister variance, floor of one hashhalf a hash, estimate toohalf a hash, variance onlytextbook variancelower is better64 draws an overlap

A variance that had seen one hash

A budget of 40,960 bits split between a HyperLogLog and a bottom-k sample answers an intersection best by weighting the two estimates by their variances, except in one corner: a sample of 160 hashes asked about sets sharing one key in a thousand, where the weighting's worst regret was 4.46. The sample was said to see nothing, report a variance of nought and be believed completely. Its variance was never nought — it was taken at one shared hash whenever none was seen — and it was believed too little, not too much. Half a shared hash in the variance gives the sample more weight and cuts the corner's regret to 3.08, not under the 2.5 predicted; half a hash in the estimate too gives 3.74 there, and 1.61 at five eighths of the budget in registers, the lowest worst regret any split and rule has reached. No weighting measured gets the corner under the sample's own 2.30: 160 hashes expecting a sixth of a shared one is a limit, not a formula.

streaming · Cardinality

Named alongside it

The objects these essays reach for when they reach for this one.

Bottom-kCardinalityHyperLogLogJaccard indexSketchError propagationRegretVarianceRelative errorState bitsWorst caseEstimator

All concepts