Select — where it appears
Named by 11 essays across 5 fields — each of them below, with the objects they name alongside it.
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.
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.
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.
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.
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.
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.
Sparse on average, dense where it gathers
The r-index keeps one suffix-array value for every run of its transform and prices the set as Elias–Fano: on 32 exact copies of 2,048 characters that is 666 values among 65,537 positions at 9.04 bits a value, as though they were spread evenly. They are not — 663 sit in one copy. Cut into chunks of 32 values, each held by whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set costs 4.48 bits a value, under the 8.05 that any representation of an arbitrary set of that size must spend on some set. At a divergence of 0.0005 the saving is a fifth, and from one character in five hundred it is nothing but the select directory, which the chunks replace with reading. On the scattered marks of an ordinary index the partition saves only that directory too.
Cuts that follow the gathering
Cutting an r-index's run-start values into chunks of a fixed count left chunk edges inside the places the values gather. Choosing the cuts as a shortest path through the sorted values was predicted to save a further tenth on exact copies by cutting once at each edge of the gathering. It cuts there, and saves more than a quarter: two chunks, one of them a bitmap of 664 values that a select must scan from its start. Capped at the chunk's old size, the optimum keeps the reads and saves 9% on exact copies and 15% at a divergence of 0.0005. On moderately drifted copies the uncapped optimum is smaller and cheap to read at once.
A select that starts near its answer
The cheapest partition of an r-index's run-start values held exact copies in two chunks, one a bitmap of 664 values that every select scanned from its start: 1,065 bits read a select. Capping the chunks bought the reads back by giving up the saving. A select sample every 64 values inside each chunk, its bits charged in the same shortest path, was predicted to bring the uncapped optimum under 150 bits a select for under 3.5 bits a value. It reads 111 for 3.45, where the cap that reads as little costs 3.68. And the middle divergences, predicted to be untouched because their chunks were short, lose two fifths of their reads to the same samples.
A sample that has to be found
A select sample every 64 values inside the cheapest partition of an r-index's run-start values cut a select's reads from 1,065 bits to 111 on exact copies. Samples by count bound how many values a select passes, not how many bits it reads, so samples every 128 bits of a chunk's vector were predicted to read a third less on the sparse, drifted sets at the same cost. They bound the scan as promised, but a rank sample does not say which sample a select needs, and finding it by binary search costs a select up to a third of what it reads. The two kinds of sample end up on one frontier, and the rank samples' advantage is that they come in finer steps.
A second level that pays in one band
A select on a chunked bit vector can be helped two ways: a select sample every t values says where to start but not how far to scan, and a rank sample every s bits bounds the scan but must be searched for. A directory with both — select samples that name a rank block, rank samples that bound the scan — was predicted to reach under 70 bits read a select for under 3.6 bits a value on an r-index's run starts over exact copies, a point neither kind reaches. It reaches 62 bits read for 3.76 bits a value, which neither kind reaches, and costs 3.73 within 70 bits where the better single kind costs 3.93; but under 3.6 bits a value it reads 84. The select sample names a block two rank samples away, not one. Across eight sets the second level saves more than a twentieth of a bit a value on three, and only between about 65 and 100 bits read a select: outside that band either single kind is as good.
Named alongside it
The objects these essays reach for when they reach for this one.
Index sizeElias fanoCompressed bit vectorSparse setR-indexBit vectorMeasurementRankTrade offDirectoryDynamic programmingInformation-theoretic bound