Generator

The same 8 summaries, combined three ways

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
The same 8 summaries, combined three waysEach row is one of the 10 heaviest keys; each column is one order of combining the same 8 per-shard summaries. Where the three columns differ, the count a query returns depends on nothing but the shape of the merge tree — 37 of the keys on this plate. The truth column is the exact count over the union and is what all three are estimating.keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order

The same 8 summaries, combined three ways

Each row is one of the 10 heaviest keys; each column is one order of combining the same 8 per-shard summaries. Where the three columns differ, the count a query returns depends on nothing but the shape of the merge tree — 37 of the keys on this plate. The truth column is the exact count over the union and is what all three are estimating.

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

5 essays call merge-shape. 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.

Where it is called

Changing this generator changes every one of these figures.

313roundconc 0.14536hashedconc 1.00309blockedconc 0.14how the arrivals were partitionedworst error over the top keysone summary, k = 32one summary, k = 256the merge of 8Space-Saving · stationary Zipf · 40,000 arrivals8 shards One pass, and no room

The partition the analysis did not mention

keytruthfoldedtreereversed16,3626,8666,8696,86923,0743,5783,5813,58131,9632,4672,4702,47041,3731,9021,9071,95451,0981,6021,6051,60569351,5121,4711,46377691,2801,2851,30686561,1601,1631,16395661,1001,1011,095105101,0511,0361,029shaded rows are keys whose count depends on the order aloneSpace-Saving, k = 32 · 8 shards · hashed37 keys move with the order Structures

The order nobody fixed

0231436845165232shards mergedkeys whose count movedthree orders:folded in one at a timecombined pairwise, in a treefolded in, last shard firstMisra-Gries, k = 32 · hashedworst gap 298 arrivals What a bound is

What a fold charges per level

weighted path lengthΣ wᵢdᵢ — what Huffman minimisescuts takenΣ over the mergesdamageworst error leftchaintreesmallest-firstlargest-first543k147k123k738k309254259388323148183403Misra-Gries · 32 shards · hashedleast path smallest · least damage balanced Structures

The fold that minimises the wrong thing

01002003004005006007008009001000roundloads 1.0×blockedloads 1.0×hashedloads 17.6×worst error over the heaviest keyschaintreesmallest-firstlargest-first32 shards · k = 32 · 40,000 arrivalseven 1.00× · uneven 2.7× What is taught wrongly

A parameter that waits for another

The library, page 3 of 5 — where merge-shape sits