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

Peak space — where it appears

The largest amount held at once during a run, which decides whether a program fits, rather than the total ever allocated over its lifetime. It is what decides whether a program fits, and it ranks structures differently from the total ever allocated, which is what an allocator charges for.

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

—execution—intention87777776569888888765one unit = one subproblem given a value100 cells computed, 20 held at once

The table nobody has to keep

A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.

space · Table —execution—intention0123456789112345667822234567773333455678434345667854444567776555555678766666656787777776569888888765one unit = one subproblem given a value110 cells for one divide step, 30 held

The alignment that fits in one line

Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.

space · Distance 0%25%50%75%100%1×1.5×2×3×4×6×shareheadroom over the mean occupancyoverflowingstanding idledrifting · 4.0 s window · 100 Hz47% overflow at the mean

Sized for a rate that does not hold still

A four-second window on a stream at a hundred arrivals a second holds four hundred items on average and between 105 and 2,169 when the rate moves. An allocation set at that average overflows at 47 per cent of instants while 35 per cent of it stands empty, which is the same decision failing in both directions at once.

practice · Window ε = 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 10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21×

The period that is not a promise

Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.

streaming · Rank

Named alongside it

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

Trade offAuxiliary spaceMeasurementAllocatorCompression scheduleDynamic programmingEdit distanceGreenwald–KhannaParameter choiceQuantile summaryStreaming modelSubproblem

All concepts