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

Select — where it appears

Where the k-th one of a bit vector is, which is not rank run backwards. Rank's directory is indexed by position and select's answers are indexed by rank, and the ones are not evenly spaced — so support for select is a separate structure, and it is what lets an ordered encoding replace a stored map.

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

1,00010,00010³bits of select supportpositions inspected, worst casebinary search, no extra bits: 510L=8L=256L=8L=256one position per L onesdense and sparse6,554 ones in 65,536 positions · sub-blocks of 8worst cases, every k

Select is not rank backwards

Rank counts the ones before a position and select finds the position of the k-th one, and only the first has an obvious structure. The constant-time answer costs 1.56 bits per one, is bounded in a unit the machine does not charge for, and on a vector with one bit in fifty it inspects more positions than the binary search it replaced.

machine · Index 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 parentheses131,07216.7%select support115,71214.8%superblock minima16,3982.1%superblock table80,97010.3%block minima147,46518.8%block tables291,25537.2%the partsbitstotal 782,872 · the segment tree 2,228,224shared lookup table 82,944, not counted65,536 values · openings in index order, found by select2.85x smaller

Two bits a value, and what undoes them

The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.

space · Range level 0 · left585 keptlevel 1 · right+351 smallerlevel 2 · right+113 smallerlevel 3 · right+39 smallerlevel 4 · right+40 smallerpositions still in play, and the half the code leaves behindsmaller symbols before position 700: 543rank of "s": 42 — from the same 5 operationsσ 21 · code 011115 ranks, not 105

The count that was already there

A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.

machine · Symbol plain bit vector19,475compressed blocks4,55723.4%Elias–Fano3,90520.1%positions, priced as Elias–Fano3,59118.4%16,385 rows · one in 32 markedElias-Fano at 20.1%

A position split in two

Write each sorted position as a high part and a low part. Store the low parts packed and the high parts as a bit vector in which the k-th one sits at position (p >> w) + k. A select on that vector and a low read recover any position.

structures · Space bits heldthe model3,591the structure3,905one rank, in operationsbinary search10 stepsselect and walk1 select + 0.7016,385 rows · one in 32 marked14x on the operation

A price with no structure under it

A class in this collection has charged Elias–Fano's price for several strands and stores an array of positions searched by binary search. The accounting is right about space to a bit per thousand and wrong about one operation by a factor of eight.

wrong · Space

Named alongside it

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

Index sizeBit vectorMeasurementRankTrade offDirectoryElias fanoOperation countRank directorySample marksSpace overheadWavelet tree

All concepts