Zipf — where it appears
Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
The counter that takes the smallest slot
Space-Saving keeps two numbers per key and they bracket the truth from both sides. On the twenty heaviest keys of a stream its mean error is a tenth of one arrival, against a hundred and ten for Misra-Gries at the same bits — and on the keys ranked past a hundred the ordering reverses.
A summary's silence is a bound, not a count
When both sides of a join are skewed towards the same values the textbook estimate is 399 times too low and the order it picks costs 244 times the better one; two counters a side repair it. Skew them towards different values and the same estimate becomes 254 times too high — and the counters have nothing to say, because no value is in both summaries. Using their silence instead repairs the middle of the sweep and makes the far end six times worse.
Named alongside it
The objects these essays reach for when they reach for this one.
Heavy hitterMisra–GriesSummaryMeasurementState bitsTrade offCardinality estimationCorrelationCount-MINExpiryGuaranteeHonest limit