Peak space — where it appears
Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
A list that gives back its places
An estimator of the third frequency moment keeps a list of candidate heavy keys beside a Count-Sketch and samples the rest, and cutting a long list at the end of the pass to the candidates that hold a share of its moment picked the right keys and paid for the whole list. Dropping a candidate during the pass, as soon as it falls below that share, was predicted to make the list's memory follow the stream: under four candidates on steep streams, within a fifth of the best fixed list, and about ten on Zipf 0.5 with most of the earlier win kept. The list ends the pass the right length — three candidates on Zipf 1 — but its memory is its peak, and the peak is set by the twenty-fifth arrival, before any key has stood out: nineteen candidates on Zipf 1, and on flatter streams the most a share θ allows, one over θ. Charged its peak, it beats the end-of-pass cut on every stream from Zipf 0.75 up, 208 words against 364 at Zipf 1, and never reaches the best fixed list, 159.
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