File RankSelect.h

↰ Parent directory (ADS/succinct)

Rank and select on a static vector of bits B of m bits with n 1s (section 15.1.1 of the notes): :math:` rank_b( i ) , the number of the bits b in :math: B[ 0 , i ) , and :math: select_b( k ) , the place of the k-th bit b, the primitives on which every succinct structure of :ref:`namespace_ADS is built (Elias-Fano, the trees by levels and by parentheses, the graphs).

Definition (ADS/succinct/RankSelect.h)

Detailed Description

rank is the two-level directory of Jacobson, with the sizes that suit the words and the caches of today: for each block of Z = 256 bits, one word of 64 bits holds the absolute rank of the block in its 40 high bits and the ranks of its words 1, 2 and 3 relative to the block in 8 bits each, and the 1s of the word up to i are the sideways sum of the masked word, which takes the place of the table of the ranks of all the small blocks of the notes (a table of :math:` 2^z z log z ` bits is affordable only with z = log m / 2, while the sum of 64 bits is one instruction); one access to the directory and one to the bits, no branch, O( 1 ) time, with :math:` 64 / 256 = 25 % ` of m bits more. The notes set :math:` Z = log^2 m ` and :math:` z = log m / 2 ` so that the directory takes o( m ) bits (Theorem 15.1); with constant blocks it takes a constant fraction, the trade of the practical designs: Vigna’s rank9 and the directory of Gog and Petri take the same 25% with two words per 512 bits, the poppy of Zhou, Andersen and Kaminsky and the flat rank of Kurpicz 3% with a sum of up to 8 words per query [see File CompactRankSelect.h]. Above :math:` 2^{40} ` bits a third level of 64 bits counts every :math:` 2^{40} ` bits.

select is the inventory of Vigna’s simple select, for the 1s and for the 0s: the 1s are cut in groups of :math:` 2^ell , with :math: ell = lfloor log_2 ( 1.5 cdot 4096 , k / m ) rfloor ` for k of them, so that a group spans between 3072 and 6144 bits; for each the place of its first 1 is kept in 64 bits, and the places of its 1s of rank multiple of :math:` 2^{ell - 5} ` in 16 bits from it, a line of the cache. :math:` select_1( k ) ` reads the place of the 1 of rank k rounded down to :math:` 2^{ell - 5} ` and counts the rest of the 1s word by word, by the sideways sums, and ends in the word by the broadword selectInWord() [see File BitVector.h]: three accesses to memory and a few words, O( 1 ) time where the 1s are spread evenly, with about :math:` 576 / 6144 ` to :math:` 576 / 3072 , 9.4% to 18.8%, of m bits more for each value. A group that spans :math: 2^{16} ` bits or more, whose offsets do not fit, is sparse, and its 1s are found by a binary search on the directory of rank between its ends, :math:` O( log ( m / 256 ) ) ` in the worst case. The notes give the scheme of Clark, which splits the blocks of :math:` log^2 m ` 1s into sparse ones, whose places are written down, and dense ones, split again with :math:` ( log log m )^2 ` 1s and ended by a table: O( 1 ) time in the worst case and o( m ) bits (Theorem 15.2), at the price of three levels whose constants are large for the sizes of practice; the inventories with constant groups are what the practical designs use (Vigna; Gog and Petri; the darray of Okanohara and Sadakane). A group of fewer than 32 bits b, below about 1% of them, keeps the place of each one, and select reads no bit at all.

The directory is built in one pass on the words: the sideways sums :math:` p_0 , ldots , p_3 ` of the words of a block, at most 64 each, are put in the bytes of a word, and one product gives their prefix sums in the bytes, which do not overflow, :math:`[ ( p_0 + 2^8 p_1 + 2^{16} p_2 ) cdot ( 1 + 2^8 + 2^{16} ) bmod

2^{24} = p_0 + 2^8 ( p_0 + p_1 ) + 2^{16} ( p_0 + p_1 + p_2 ) , ` the three relative ranks of the entry; from words in memory the words are copied in the same pass, above :math:` 2^{23} ` bits, where reading them twice costs more than a copy in the caches. The inventories of select are built in the constructor (RankSelect, the default), or by the first select of each value (LazyRankSelect), in a pass on the directory, so that a structure that only ranks never pays for them; the first call builds an inventory once, whichever the threads that call it (with std::call_once, and a flag read with acquire semantics before it), and a copy keeps the inventories already built. The lazy form costs select 10 to 15%: the load of the flag with acquire semantics makes the compiler read the fields of the inventory again at each query, which the eager form, with no flag at all (the template parameter Lazy), keeps in plain fields.

The places count from 0: :math:` rank_1( i ) ` here is :math:` Rank_1( i ) ` of the notes on the places :math:` 1 , ldots , i , and :math: select_1( k ) ` here is :math:` Select_1( k ) - 1 ` (in Example 15.1, :math:` rank_1( 6 ) = 2 ` and :math:` select_1( 3 ) = 7 `).

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 RankSelect.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 15

  1. Jacobson, Space-efficient static trees and graphs, Proc. 30th FOCS, 549-554, 1989, doi:10.1109/SFCS.1989.63533

  1. Clark, Compact Pat Trees, PhD thesis, University of Waterloo, 1996

  1. Gonzalez, S. Grabowski, V. Makinen, G. Navarro, Practical implementation of rank and select queries, Proc. 4th WEA, 27-38, 2005

  2. Vigna, Broadword implementation of rank/select queries, Proc. WEA 2008, LNCS 5038, 154-168, 2008, doi:10.1007/978-3-540-68552-4_12

  1. Zhou, D. G. Andersen, M. Kaminsky, Space-efficient, high- performance rank and select structures on uncompressed bit sequences, Proc. SEA 2013, LNCS 7933, 151-163, 2013, doi:10.1007/978-3-642-38527-8_15

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

  2. Navarro, E. Providel, Fast, small, simple rank/select on bitmaps, Proc. SEA 2012, LNCS 7276, 295-306, 2012, doi:10.1007/978-3-642-30850-5_26

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Typedefs