Concept

Heavy tail — where it appears

A distribution whose extreme values are a large share of its range, so that an error tolerated at the median is worthless at a high percentile. An error tolerated at the median is worthless at a high percentile of one, which is why a summary's promise has to name the part of the distribution it covers.

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

What a second pass buys

Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.

space · Pass

An error measured against the answer

A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.

streaming · Rank

The digest that promises nothing

The t-digest is the quantile structure most widely deployed and the only one with no proven bound on its rank error at any quantile. Measured, it beats the structure that does have one — and on two clusters with a gap between them it returns 431.5, where the data holds nothing at all between 40 and 800.

wrong · Rank

Named alongside it

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

Measurement Greenwald–Khanna Guarantee Honest limit Quantile Rank error State bits Summary Tail Trade off Complexity class Counterexample

All concepts