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

Merging — where it appears

Combining two summaries into one describing the concatenated stream, which some structures do exactly and others do only at a further loss. Some structures do it exactly and others only within their guarantee, and the difference decides what a distributed pipeline may safely retry.

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

1,8103,6205,4297,239010,00020,00030,00040,000arrivals so farcount of key 1 in the last 4,096Misra-Gries, no clockblocks of Misra-Griesthe truth, and the ring buffera heavy hitter that stops · sampled every 5006,493 claimed, 0 true

The count that outlives its arrivals

A Misra-Gries counter holding six thousand is not a record of six thousand arrivals. It is a number that has been added to and taken from, and nothing in the structure says when any of it happened — so when the key stops arriving the counter stays, and goes on reporting a key with nothing in the window as the heaviest thing in it.

structures · Window 2585167741,032020,00040,000arrivals so farcountSpace-Saving's floorMisra-Gries's decrementsboth 93840,000 prefixes, 0 disagreementsk = 32 against k = 31

Two structures that are one

Space-Saving never underestimates and Misra-Gries never overestimates, and they are taught as rival structures with opposite failure modes. Subtract one number from every Space-Saving counter and what is left is the Misra-Gries table, key for key and count for count, at all twenty thousand prefixes of a stream and at every table size tried.

wrong · Sketch

Named alongside it

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

Heavy hitterMeasurementMisra–GriesConstant factorCounterexampleExpiryFalsificationGuaranteeHonest limitMergeable summaryOne-sided errorReproducibility

All concepts