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

Bottom-k — where it appears

A cardinality summary keeping the k smallest hash values seen, whose retained keys are also a uniform random sample of the distinct ones. The retained hashes double as a uniform sample, so one structure answers a distinct count and supports a second question nothing else here can.

Named by 3 essays across 3 fields — 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 10,0000.1total bits of stateruns outside ±15%1 × 483 × 485 × 487 × 489 × 48240 runs per design · tolerance ±15% · truth 12,00067 → 3 failures

The estimate that is a median of means

An estimator with a 70% spread is not usable and an estimator with a stated failure probability is. The construction that turns the first into the second is two lines long, it is where every delta in this field comes from, and its exponential is measured here by counting failures rather than by evaluating a bound.

randomness · Sketch HyperLogLog1024/1024 identicalCount-Min256/256 identicalbottom-k128/128 identicalMisra-Gries20/36 identicalfraction of the state that merged to the identical value→ 1,974→ 10,291→ 2,322→ 8,766two streams of 30,000 · 2,007 distinct keys in the union3 of 4 merge exactly

The summaries that add

Two sketches built over two streams and merged are, for three of the four structures here, byte for byte the summary the concatenated stream would have produced. For the fourth the guarantee survives and the state does not, and calling both properties mergeability hides the difference that matters.

structures · Cardinality

Named alongside it

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

EstimatorSketchState bitsCardinalityGuaranteeHyperLogLogMergeable summaryRelative errorConcentrationCount-Min sketchDeterministic algorithmError propagation

All concepts