File CompactRankSelect.h

↰ Parent directory (ADS/succinct)

Rank and select on a static vector of bits B of m bits in about 3.5% of m bits more, the compact counterpart of RankSelect [see File RankSelect.h], which spends about 50% for the fastest queries: the flat directory of Kurpicz, after the poppy of Zhou, Andersen and Kaminsky.

Definition (ADS/succinct/CompactRankSelect.h)

Detailed Description

The bits are cut in superblocks of 4096 bits, each one in 8 blocks of 512 bits, a line of the cache [see File BitVector.h]. One entry of 128 bits per superblock holds the 1s before it since its top region of :math:` 2^{32} ` bits, in 32 bits, and the 1s before each of its blocks since the superblock, :math:` c_0 = 0 , c_1 , ldots , c_7 le 3584 `, in 12 bits each; a count of 64 bits per top region completes the rank. Hence :math:`[ rank_1( i ) = T[ lfloor i / 2^{32} rfloor ] +

S[ lfloor i / 4096 rfloor ] + c_{lfloor i / 512 rfloor bmod 8} + sum_{j < 8} | w_j wedge ( 2^{min( 64 , max( 0 , o - 64 j ) )} - 1 ) | , ` with o = i mod 512 and :math:` w_j ` the words of the block: one access to the entries, one to the line of the block, and the sideways sums of its 8 words cut at i, with no branch (with AVX2, the bytes of the line before the one of i counted 32 at a time by a table of the 16 nibbles, the method of Mula, Kurz and Lemire); :math:` 128 / 4096 = 3.125 % ` of m bits.

select keeps the superblock of every 4096-th bit b, 32 bits each, at most :math:` 32 / 4096 < 0.8 % ` of m bits for each value, and finds the k-th bit b by a binary search on the entries between two samples, then the block by the 7 counts of the superblock and the word by the sums of the 8 words of its line, both by comparisons with no branch, and the bit by selectInWord(); :math:` O( log ( m / 4096 ) ) ` steps in the worst case and O( 1 ) where the bits b are spread evenly (a sample every 2 to 8 superblocks for a density between 1/2 and 1/8). The trade with RankSelect is the one of the literature: a sum of up to 8 words and a search of the entries instead of one word and an inventory, in 15 times fewer bits.

The directory and the samples are built in one pass on the words, a superblock at a time with no test on the words that exist; from words in memory the words are copied in the same pass, above :math:` 2^{23} ` bits, as in RankSelect.

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 directory agrees with a scan. The functions are defined in CompactRankSelect.tpp.

  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. Zhou, D. G. Andersen, M. Kaminsky, Space-efficient, high-performance rank and select structures on uncompressed bit sequences, Proc. 12th SEA, LNCS 7933, 151-163, 2013, doi:10.1007/978-3-642-38527-8_15

  1. Navarro, Compact Data Structures, Cambridge University Press, 2016, chapter 4, doi:10.1017/CBO9781316588284

  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

  1. Pandey, M. A. Bender, R. Johnson, A fast x86 implementation of select, arXiv:1706.00990, 2017

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes