Concept

Second frequency moment — where it appears

The sum of the squared key frequencies of a stream, which measures its skew and which no counter can reach by counting anything. No counter reaches it by counting anything, which is why estimating it needs signs and squares rather than tallies.

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

Also named here as tug-of-war — the same set of essays touches all of them, so they are one junction rather than several.

The estimate that squares the stream

The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.

streaming · Moment

The independence an estimator spends

Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.

randomness · Moment

A sketch that is allowed to be under

Count-Min's estimate is never below the truth, and it pays for that with an error proportional to the whole stream. Give every key a sign and take a median instead, and the same table is 2.7 times more accurate on the keys anybody asks about — and wrong in both directions.

structures · Moment

Named alongside it

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

Estimator Tug-of-war Unbiased estimator Hash family Median of means Sketch State bits Variance Zipf distribution Additive error Adversarial input Count-Min sketch

All concepts