The other axis

Measuring what an algorithm keeps

The alloc and enter primitives, why a call stack is auxiliary space that no array counter reaches, and why peak and total have to be tracked separately rather than summarised as one number called "space".

The stack nobody counts

Recursion depth as auxiliary space — why total calls and peak depth are different numbers, the three space profiles of one traversal, and the two-line change that bounds quicksort's stack on every input.

The frontier between time and space

The Pareto set over comparisons and peak auxiliary space, what being dominated means that being slower does not, and how completely the frontier is rearranged by changing the input.

The space the model does not see

The limits of counting auxiliary space in slots — bytes, allocator overhead, the excluded input, the interaction with cache — and why the time–space product bound was attempted and cut rather than quoted.

The table nobody has to keep

Why the number of cells a dynamic program computes and the number it holds at once are independent resources, what a rolling frontier costs, and the answer it can no longer give.

The alignment that fits in one line

Hirschberg's divide and conquer for linear-space alignment, why the extra work is exactly twice and not approximately, and what the general time-for-space exchange looks like.

The clock that cannot see the burst

Why a clock's resolution is a floor on the burstiness a system can observe, what a timestamp costs as the resolution is refined, and why the resolution is almost never a decision anybody made.

What a window costs in bits

State against window length for the exponential histogram, the crossover with keeping the window outright, and where the bits actually go.

The text that does not have to be kept

Extraction and location from a self-index — why reproducing the text is what makes the size claim mean anything, and the sampling rate that trades bits against the work of turning a row into a position.

What a second pass buys

Peak state against passes for exact selection — the interval that narrows, the exponent fitted to the sweep, and why a split rule that needs no data is a bet on the distribution.

What is still proportional to n

The term a run-length index does not remove — why the sampling is proportional to the length, what fraction of the structure it becomes, and what changing it costs.

The cheap tail and the expensive merge

How the choice of error function decides both the size of a quantile summary and the exponent its merged size grows by, and why the two effects point the same way.

The tuples a summary does not report

Why a quantile summary's peak is its resident size plus its compression period, what that ratio is across ε, and why the number the structure reports is the wrong one to size an allocation from.

Every occurrence at the same price

Why the size-against-locate trade a sampling rate buys is a curve, and what it means that a structure sized by the run count is not on it.

The character that costs a chain

Why an index built on a parse produces a character by following copies, how deep those chains get, and what bounds them — which is nothing.

The structure paid for before the first query

What a range structure costs in bits before any query is asked, where the o(z log z) actually goes, and how much of the grid the index was already paying for.

The term that came back

What happens to a structure sized by a measure of repetition when the constraint that makes it readable is tightened all the way, and what the collapse says about the measure.

A bound that has to be paid for

What a lower-bound pruning costs in space, why the second index cannot be avoided, and how a saving in one currency is paid for in another.

One separator, or one for each

What each way of separating documents costs an index, why the cost is invisible until the alphabet crosses a power of two, and which structures require the expensive one.

Two bits a value, and what undoes them

What a succinct range minimum actually costs, in the parts the published bound is a sum of, and why the term that decides it is the map from an index to its parenthesis.

The structure that was supposed to halve

What a bidirectional index actually costs, why the second transform cannot be avoided, and what a structure named as a space fix turned out to be a fix for instead.

A bit for every bit

What a wavelet tree over a permutation costs, where its entropy is, and why a structure whose levels are balanced by construction has almost nothing for a compressor to take.

An index that cannot locate

A counting-only FM-index built, stripped and measured, with the parts it keeps, the parts it drops, and what a bidirectional index costs when one half is that.

What the chain cost

The size of the previous-occurrence chain measured against every other part of a document index, and what the apparatus costs once it is gone.

Two currencies for one separator

The three document joins priced in packed bits and in runs of the transform, and why the two answers diverge as a collection is cut more finely.

The array that says where is twice the samples

Where an FM-index's locating apparatus actually is, why the marks do not shrink when the sampling thins, and the floor every curve in the strand flattens onto.

The apparatus, three times smaller again

The document-listing apparatus priced at three stages, what each removal was worth, and where the remaining bits are.

The ladder, and the rung that spends

Three size changes to a bidirectional index applied cumulatively, and a fourth step that converts all of them into speed at almost no net size.

Half an index is three permutations

Where a Lempel–Ziv index's bits actually are, the permutation that is derivable from its neighbour, and a time-for-space choice never priced here.

Sparse on average, dense where it gathers

The run-start values of an r-index over 32 copies of 2,048 characters of English, drifted at divergences from 0 to 0.01, against the marks of an FM-index sampled one row in 32: the run-start values along the collection; bits a value as compressed blocks, as one Elias–Fano and partitioned into chunks that each choose a bitmap, their own Elias–Fano or a run; the chunks' forms along the set; bits a value against chunk size and against divergence; and the bits a select reads at each chunk size.

Cuts that follow the gathering

The run-start values of an r-index over 32 copies of 2,048 characters of English, drifted at divergences from 0 to 0.01, and the marks of an FM-index sampled one row in 32, partitioned by the cheapest set of cuts — a shortest path through the sorted values, its upper-level charge re-estimated until it settles — with and without a cap on the values a chunk holds: where the cuts fall along the collection, bits a value against one Elias–Fano, fixed chunks and the floor for an arbitrary set, bits against the bits a select reads, the saving under each cap, and how large the optimum's chunks are.

A select that starts near its answer

The run-start values of an r-index over 32 copies of 2,048 characters of English, drifted at divergences from 0 to 0.01, and the marks of an FM-index sampled one row in 32, partitioned by the cheapest set of cuts with and without a cap on chunk length, and with a select sample every 256, 64 or 16 values inside each chunk charged in the shortest path: bits a value against bits a select reads on exact copies, at 0.0005 and at 0.01, the reads of the uncapped optimum, the capped one and the sampled one on every set, and what the samples cost in bits and in chunks.

A sample that has to be found

The run-start values of an r-index over 32 copies of 2,048 characters, drifted at divergences from 0 to 0.01, and the marks of an FM-index, partitioned by the cheapest uncapped set of cuts with select samples every 256, 64 or 16 values or rank samples every 1,024 to 64 bits of each chunk's scanned vector, all charged in the shortest path: bits a value against bits a select reads on exact copies, at 0.005 and at 0.01, what a select reads in the search over rank samples and in the scan after it, and the smallest index of either kind within a budget of reads on every set.

A second level that pays in one band

The run-start values of an r-index over exact copies, over copies at divergences from 0.0002 to 0.01, and over scattered marks, cut into the cheapest uncapped partition of plain, Elias–Fano and run chunks with every directory's bits charged in the path. Select samples alone, rank samples alone, and a two-level directory with a select sample every 64, 128 or 256 values holding a rank block's number and rank samples every 64, 128 or 256 bits: bits a value against bits read a select on exact copies and at divergence 0.01, what a two-level select reads by part on every set, the rank samples it steps, and the saving per set at two budgets of reads.