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

Resource accounting — where it appears

Naming what a structure's bits are spent on, in parts required to sum to the total, so that a size can be argued with rather than quoted. The parts are required to sum to the total on every call, because a total cannot show that one of its terms is the majority of it.

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

elements of block written per key insertedB-tree, in place49.3Log-structured, T = 23.0 · 16× less than the treeLog-structured, T = 42.0 · 25× less than the treeLog-structured, T = 81.0 · 49× less than the treeLog-structured, T = 161.0 · 49× less than the treeB = 64, M = 4,096 (M/B = 64)25× between the two structures at T = 4

The writes nobody counted

Sixteen thousand keys inserted into a B-tree write 49.3 elements' worth of blocks for every key stored. The same keys into a log-structured store write 2.0. Every operation counter reports the two as the same work — the same insertions, the same comparisons, the same number of updates — and the factor of 24 decides which structure a storage engine is built from.

applied · Transfer 10³10⁴10³10⁴10⁵nrandom bitsskip list, one build — ntreap, one build — nreservoir, Algorithm R — n log nn from 256 to 16,384bits charged including rejections

Counting the coin flips

A skip list spends 2.03 random bits per key and a treap spends exactly 32. Reservoir sampling spends 1,356,399 bits on a stream of 65,536 and a better version spends 9,380. None of those numbers appears in any complexity class any of these structures is described by, and none of the site's other three counters can see them.

counting · Count windowed HyperLogLog4,088 bitsone stamp per live key8,775 bitsblocks of Misra-Gries18,549 bitsthe last W keys, kept131,072 bitskeysstampspayloadindexthe parts, in the order they stackwindow 4,096 · the popular keys drift131,072 bits at most

The bits that say when

A windowed cardinality estimator holds 4,592 bits and 2,392 of them are clocks. Every summary in this collection has reported its size from the shape of its own structure, and not one of those numbers has ever been asked what the bits were for — so the resource that half of these structures spend most of their state on has been invisible while being counted.

streaming · Window 010020030040021φ 382φ 7203φ 17434φ 42885φ 1012486φ 242measured 409counts chargedlevel of the foldcharged at this levelrunning total64 shards · k = 32 · hashedcharged 409 · measured 409

The floor charged at every level

A key surviving a fold of sixty-four shards is charged 2, then 8, then 20, then 43, then 88, then 248 — the floor of whatever summary it was merged against, level by level. They sum to 409, and the damage read off the merged table is 409. The model that charged sixty-three copies of the leaf floor said 222.

floors · Floor ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14%

The tuples a summary does not report

A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

space · Space 101001,00010100total length of the pattern settimes the published rule's precomputationwritten as a definitionbuilt from the linksthe published rulefour symbols · m = 10137x becomes 1.60x

The ratio that was an implementation

This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.

wrong · Symbol

Named alongside it

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

MeasurementTrade offMeasured countState bitsAllocatorAuxiliary spaceB-treeBad-character ruleBlock transferCacheCommentz-walterComparison count

All concepts