File InterleavedRankSelect.h

↰ Parent directory (ADS/succinct)

Rank and select on a static vector of bits B of m bits with the counts inside the lines of the bits, the layout of SPIDER of Laws, Bliven, Conklin, Laalai, McCauley and Sturdevant: a line of the cache of 512 bits holds 496 bits of B and, in its first 16 bits, the 1s before it since its superblock of 128 lines (63488 bits, so that the count fits), and a superblock keeps the 1s before it in 64 bits apart.

Definition (ADS/succinct/InterleavedRankSelect.h)

Detailed Description

Hence :math:`[ rank_1( i ) = S[ lfloor ell / 128 rfloor ] + h_ell +
B_ell [ 0 , i bmod 496 ) | , qquad ell = lfloor i / 496

rfloor , ` :math:` h_ell ` the count of the line :math:` ell ` and :math:` B_ell ` its bits, with one access to the memory of the vector, the line, against two of the directories kept apart [see File RankSelect.h, File CompactRankSelect.h] (the array of the superblocks, 1 word per 63488 bits, stays in the caches); the sum of the line is that of CompactRankSelect, 32 bytes at a time by a table of the nibbles with AVX2. The counts take :math:` 16 / 512 = 3.125 % ` of the line.

select keeps the line of every 8192-th bit b with the bits b before that line (96 bits each, at most :math:` 96 / 8192 < 1.2 % ` of m bits for each value) and guesses the line of the k-th bit b between two samples by interpolation, as SPIDER does, :math:`[ hatell = ell_j + frac{ ( k - 1 - c_j ) ( ell_{j+1} - ell_j ) }

{ c_{j+1} - c_j } , ` :math:` c_j ` the bits b before the line :math:` ell_j , corrects the guess a line at a time by the counts of the lines (a step or two where the bits b are spread evenly, :math: ell_{j+1} - ell_j ` in the worst case), and ends in the line by the sums of its words and selectInWord() [see File BitVector.h].

The contracts [see File Contract.h]: :math:` i le m ` for rank and :math:` 1 le k ` up to the number of the bits b for select; the postconditions are that the bit at :math:` select_b( k ) ` is b and that its rank is k - 1, and the audit of the construction is that the counts agree with a scan. The functions are defined in InterleavedRankSelect.tpp.

    1. Laws, J. Bliven, K. Conklin, E. Laalai, S. McCauley, Z. S. Sturdevant, SPIDER: improved succinct rank and select performance, Proc. 22nd SEA, LIPIcs 301, 21, 2024, doi:10.4230/LIPIcs.SEA.2024.21

  1. Kurpicz, Engineering compact data structures for rank and select queries on bit vectors, Proc. 29th SPIRE, LNCS 13617, 257-272, 2022, doi:10.1007/978-3-031-20643-6_19

  1. Mula, N. Kurz, D. Lemire, Faster population counts using AVX2 instructions, The Computer Journal 61(1), 111-120, 2018, doi:10.1093/comjnl/bxx046

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes