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

Idempotence — where it appears

The property that combining a summary with itself changes nothing, which makes a shard delivered twice harmless and holds for maxima and not for sums. It holds for a structure whose combination is a maximum and fails for one whose combination is a sum, which decides what a distributed pipeline may retry.

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

keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order

The order nobody fixed

The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.

structures · Merge 01325leading-zero rank keptregister, 0 to 255estimate 7,107truth 7,368error -3.54%0 still empty256 registers × 5 bits = 1,280 bitspredicted ±6.50%

A count read off the leading zeros

Hash every key and watch for the longest run of leading zeros. Seeing k of them is evidence of about two to the k distinct keys — an estimator with a variance so large it is worthless, and the two devices that fix it are the whole of what a cardinality sketch is.

streaming · Cardinality 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.

Mergeable summaryCardinalityDeterministic algorithmEstimatorGuaranteeHash functionHyperLogLogMisra–GriesOne passSketchState bitsAssociativity

All concepts