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 2 essays across one field — each of them below, with the objects they name alongside it.

Also named here as inclusion exclusion, 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

Named alongside it

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

Bottom-kCardinalityHyperLogLogInclusion exclusionJaccard indexRelative errorSketchState bitsEstimatorHonest limitMergeable summaryRegret

All concepts