Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Associativity — where it appears

The property that combining several things gives the same result however they are grouped. A merge that discards information rarely has it, so the shape of the merge tree becomes a silent parameter of the answer — exactness and order-blindness travel together, and a structure that throws anything away has neither.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

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 order nobody fixed

The same eight summaries, combined pairwise in a tree or folded in one at a time, produce tables that differ on forty keys — the largest by 964 arrivals. Nothing in a deployment fixes which shape is used, and both answers are inside the guarantee.

structures · Merge 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 fold charges per level

Thirty-two counter tables folded in a chain come out wrong by 323 where the same thirty-two combined pairwise are wrong by 148, and the quantile summaries prefer the chain by exactly as much in the other direction. What is being charged in each case is the depth of the fold, and the two families are charged on opposite ones.

bounds · Merge folded in one at a time2,616 tuples17 ranks outcombined pairwise, in a tree3,637 tuples17 ranks outfolded in, last shard first2,615 tuples17 ranks outtuples kept, and worst rank error against a promise of 10032 shards · ε = 0.01 · high-biased · round1.39× the space, 0 ranks of answer

The shape that moves the bill

Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.

structures · Rank

Named alongside it

The objects these essays reach for when they reach for this one.

GuaranteeMerge treeMergeable summaryMisra–GriesShardSpace-savingHeavy hitterQuantile summaryTrade offDeterministic algorithmFixed pointGreenwald–Khanna

All concepts