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

Error propagation — where it appears

How the errors of measured or estimated quantities combine when a result is computed from them. A sum of independent errors grows as the root of their squares, and a difference of correlated estimates can be far more accurate than that rule predicts.

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

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

Named alongside it

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

Bottom-kCardinalityHyperLogLogInclusion exclusionJaccard indexSketchRegretRelative errorState bitsVarianceWorst caseEstimator

All concepts