Signed error on 200 keys, in the general turnstile model

Signed error on 200 keys, in the general turnstile model

Each mark is one key's estimate minus its exact count, so a mark left of the line is an estimate BELOW the truth. The stream is 60,000 updates over 2,048 keys, insertions and deletions, counts may go negative. Count-Min 4×64 holds 8,192 bits and came back under on 184 of 200 keys, worst under -161 and worst over 13; Count-Sketch 4×64 holds 8,192 bits and came back under on 99 of 200 keys, worst under -54 and worst over 39. Count-Min's one-sidedness is a consequence of every cell being a sum of non-negative counts; it survives deletions exactly as long as no count goes below zero, which is a condition on the stream that the structure cannot check and its bound never mentions.

Drawn at 700 × 316, wide on the page. Everything above is what turnstile-errors 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 turnstile-errors. 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.