Grid — where it appears
Named by 9 essays across 4 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
PermutationWavelet treeMeasurementIndex sizeBit vectorTrade offCompressionOutput-sensitiveRange reportingRank directorySpace overheadControl