Space lower bound — where it appears
Named by 5 essays across 3 fields — each of them below, with the objects they name alongside it.
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
A floor on the bits
Answering membership for n keys with a false-positive rate of 1% and no false negatives requires at least 6.64 bits per key, whatever the structure. A Bloom filter uses 9.59. The gap is 44.27% at that rate and at every other rate, and it is the first bound on this site that a real structure comes close to.
What a window costs in bits
The approximate structure grows like the square of a logarithm and the exact one grows like the window, so the approximation wins eventually. Eventually is a window of 6,000 at a 2% tolerance — and below it the summary is larger than the thing it is summarising.
The floor under a summary
An exact one-pass distinct-counter over a universe of u keys needs at least log2 of u-choose-u-over-2 bits of state — the same counting argument as the sorting floor, applied to memory states instead of outcomes. At u = 12 that is 9.85 bits, and an eight-bit candidate is shown to collide by running all 924 subsets.
The floor under a window
An exact count of the ones in the last W arrivals needs W bits, and the argument is a pigeonhole that can be performed rather than quoted — 1,024 windows, an eight-bit state, the colliding pair produced, and the two answers it cannot tell apart.
Named alongside it
The objects these essays reach for when they reach for this one.
State bitsCounting argumentHonest limitInformation-theoretic boundLower boundExpiryExponential histogramGuaranteeMeasurementPigeonholeSliding windowStream model