Space-Saving's bracket is empty where the answers matter and 937 wide where they do not

Space-Saving's bracket is empty where the answers matter and 937 wide where they do not

The 4 heaviest and the 4 lightest of the 32 counters in a Space-Saving summary over 40,000 arrivals. Each bar runs from the key's lower bracket — its counter minus the value it inherited when it took a slot — to the counter itself, and the mark is the true count. The structure holds both ends and reports the upper one, which is why it is described as never underestimating; the other end is a thing Count-Min does not have at all. 3 of these 8 rows have no bracket: a key that took a slot before the table filled inherited nothing, so its counter is its exact count. The wide ones are at the bottom, where a key inherited the 938 that the evicted key had accumulated. So the structure is exact precisely on the keys anybody asks it about, and uncertain on the ones it is about to forget. Misra-Gries's shortfall bound over the same stream is 1,250.

Drawn at 700 × 368, wide on the page. Everything above is what counter-shift returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

3 essays call counter-shift. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.