Space-Saving merged from 8 shards: worst error over the top 8 keys

Space-Saving merged from 8 shards: worst error over the top 8 keys

The three-way comparison, over 40,000 arrivals of stationary Zipf — the control, where a window is a smaller sample partitioned hashed by key: every key on one shard. The merge of 8 summaries of 32 counters is wrong by at most 536 on the heaviest keys. One summary of 32 counters — an eighth of the state — is wrong by 769, which makes the merge look good. One summary of 256 counters, which is exactly the state the shards were holding between them, is wrong by 0. The merge is the price of never having the whole stream in one place, and it is paid against the middle bar rather than the top one.

Drawn at 700 × 240, wide on the page. Everything above is what merge-against-matched 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 merge-against-matched. 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.