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

Grid — where it appears

A set of points on a plane whose axes are two orderings of one collection of objects. Search problems that impose two conditions at once become rectangles over one, which is why a range structure over a grid replaces a scan proportional to a range with a descent proportional to a logarithm.

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

rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing

The candidates a filter cannot avoid

A phrase index answers a search by intersecting two ranges of boundaries, and it does the intersection by walking the smaller one. On a collection of thirty-two copies that is 4,355 phrase examinations to produce 32 occurrences — 136 examinations each, and rising.

indexes · Grid phrase table5,148 bitsboundary orders3,744 bitsintersection grid1,696 bitspropagation grid1,544 bitsz = 156 · ⌈log₂ z⌉ = 8 levels16,384 characters · 12,132 bitsgrids 26.7% · 20.8 bits a point

The structure paid for before the first query

The two grids that make a phrase index's search proportional to its answer are 3,240 bits on an 8,892-bit index — twenty-seven per cent of the whole structure, answering nothing on their own, and 38% of them is rank directory rather than payload — the lower-order term of the published bound, measured.

space · Grid plain51,600block-coded47,6687.6%run-coded60,805-17.8%plain, uniform51,600block-coded, uniform50,2422.6%run-coded, uniform67,121-30.1%bits · the lower three are a permutation with no structure3,612 points7.6% against 2.6%

A block, a class and an offset

Replacing each block of a bit vector by how many ones it holds and which arrangement it is takes 7.6% off the grid. On a permutation with no structure at all it takes 2.6%, so five of the seven points are the data and two of them are the encoding.

indexes · Grid rank among the boundaries, sorted by the text before themsorted by the text after0 in the rectanglepattern "ss is un"split after 40 end with the left half0 begin with the rightEnglish-like · 2 copies of 512z = 156 · 0 crossing

A rectangle over a permutation

Two orderings of one set of boundaries are two permutations, so a phrase index's intersection is a rectangle over a permutation grid — the one point set a wavelet tree stores exactly, at one bit per point per level and no coordinates at all.

structures · Grid 00.2500.5000.750101234567891011level of the wavelet treebits a bitthe parse's grida uniform permutation3,612 points · 12 levels0.997 bits a bit

A bit for every bit

A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.

space · Grid 024601234567891011level of the wavelet treemean runthe parse's grida uniform permutationbreak-even3,612 points · 12 levels1.23x chance

The runs a permutation does not leave

A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.

structures · Grid candidates, filtering4,355candidates, grid33rank and select, grid2,471occurrences32one query · same collection · same answer16,384 characters · 32 occurrencescandidates 132x · operations 1.76x

The operations a candidate count leaves out

The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.

wrong · Grid 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

Named alongside it

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

MeasurementPermutationWavelet treeBit vectorIndex sizeCompressionOutput-sensitiveRange reportingRank directorySpace overheadTrade offControl

All concepts