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

Deferral — where it appears

A piece of work named and not done, written down so that it can be taken up later. Its value is that a structure named and not built is a structure whose constants are unknown, and naming one is what makes the difference between an expectation and a measurement.

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

one index35,3354.31 bits/charthe forward half35,3354.31 bits/charthe reverse half35,3354.31 bits/charboth, which is the structure70,6708.63 bits/charbits8,192 characters · sample 322.00x one index

The structure that was supposed to halve

A bidirectional index holds the transform of the text and the transform of its reversal — 35,335 bits each, 70,670 together, exactly twice one index. The deferral that named it hoped it would stop the index doubling. It does not remove the doubling; it reuses it.

space · Distance 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters

The level where compression stops paying

Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.

wrong · Grid 00.2500.5000.750101020304050thousands of bitsrectangles counted exactlythe floorcut to d levels, the index'scut to d levels, drawnevery k-th point, the index'severy k-th point, drawnexact: right to the nearest point3,612 points

A count that names every point

A grid that can report the points in a rectangle can be no smaller than log₂(z!) bits, because reporting them recovers the permutation. A grid that only counts them was left open as possibly smaller. Exactly, it cannot be: counts alone decode every point, and on the phrase index's 3,612 points 42,860 count questions recover the whole permutation, so an exact counter pays the same floor of 37,485 bits. Approximately it can — and the rectangles a phrase index asks are where an approximate count is worst. They hold 2.6 points on average and a third of them hold exactly one; the wavelet grid cut to eight of its twelve levels, 8% under the floor, counts 46% of them right.

indexes · Grid 00.2500.5000.750124681012levels of the grid keptshare of splitsnine in tenempty splitsturned awayoccupied splitsanswered yes4,300 bits a level with its directorythe rest: maybe

A test that is the top of the search

A phrase index asked whether a pattern occurs only needs to know, split by split, whether a rectangle of its grid holds a point. Stopping the grid's descent at six of its twelve levels was predicted to turn away nine in ten of the splits that come to nothing, for half the grid's bits. It turns away three in four, and the ones it lets through sit a median of five rows from a point. The test is never wrong, but the existence query had little left for it to save: patterns that occur are settled by their first split 94% of the time, and most patterns that do not occur never reach the grid.

indexes · Grid

Named alongside it

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

Index sizeTrade offGridPer levelPermutationWavelet treeLower boundMeasurementBackward searchBidirectional indexBreak-evenCompression

All concepts