Which structure is valid in which model, and what the violation costs

Which structure is valid in which model, and what the violation costs

A filled cell is a structure that declares itself valid in that model. An outlined cell is one that will run there without complaint and whose guarantee says nothing about it — and the number in it is what that costs, measured on a general turnstile stream of 40,000 updates over 2,048 keys with a deletion rate of 0.5, on which 796 keys end with a negative count. Count-Min came back BELOW the true count on 1,758 of 1,895 keys, which its own theorem forbids and which nothing in the returned number reveals; Count-Sketch, which promises nothing about the direction of its error, came back below on 48% of them, as it is designed to. The models differ in four dials: whether an update may be negative, whether a count may end negative, whether items expire, and how many passes are allowed.

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

4 essays call model-check. 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.