Fast Select Queries Using Hybrid Bitvectors

Consider a bitvector $B\in {\{\mathrm{𝟶},\mathrm{𝟷}\}}^n$. The basic idea of the hybrid bitvector is to split the bitvector $B$ into blocks of size $b=256$ and encode each block independently, choosing the most space-efficient of the following three encodings:

1. 1.

   Minority encoding: a list of all occurrences of the rarely occurring bit $c\in \{0,1\}$.

2. 2.

   Run-length encoding: a list of positions marking the ends of maximal runs of equal bits.

3. 3.

   Plain encoding: all bits stored sequentially using $b$ bits.

For any bitvector $B^{\prime }$, let $\mathrm{enclen}(B^{\prime })$ denote the total size of the encoding (in bytes) of $B^{\prime }$ after splitting it into blocks of size $b$ and independently encoding each using the smallest of the three methods listed above. By $\mathrm{popcount}(B^{\prime })$ we denote the number of ones in $B^{\prime }$.

In the hybrid encoding of the bitvector $B$, the blocks are further grouped into superblocks of $k_s$ blocks (that is, $k_{s}b$ bits) and into hyperblocks of $k_h$ blocks (that is, $k_{h}b$ bits). The value $k_s$ is a parameter of the hybrid bitvector; the default value in the implementation is $k_s=16$. The number of blocks per hyperblock is fixed at $k_h=2^{23}$.

By ${\mathrm{block}}_B(i)$, ${\mathrm{sblock}}_B(i)$, and ${\mathrm{hblock}}_B(i)$ we denote the $i$th block, the $i$th superblock, and the $i$th hyperblock of $B$, respectively. By ${\mathrm{blockrank}}_{B,c}(i)$, we denote the number of $c$s in the superblock of $B$ containing ${\mathrm{block}}_B(i)$ prior to its beginning. Similarly, by ${\mathrm{sblockrank}}_{B,c}(i)$, we denote the number of $c$s in the hyperblock of $B$ containing ${\mathrm{sblock}}_B(i)$ prior to its beginning. Finally, by ${\mathrm{hblockrank}}_{B,c}(i)$, we denote the number of $c$s prior to the beginning of ${\mathrm{hblock}}_B(i)$ in $B$. By ${\mathrm{blockoffset}}_B(i)$, we denote the total encoding size of all blocks in the superblock containing ${\mathrm{block}}_B(i)$ that are to its left. Similarly, by ${\mathrm{sblockoffset}}_B(i)$, we denote the total encoding size of all blocks in the hyperblock containing ${\mathrm{sblock}}_B(i)$ that are to its left. Finally, by ${\mathrm{hblockoffset}}_B(i)$, we denote the total encoding size of blocks that are to the left of ${\mathrm{hblock}}_B(i)$ in $B$. See Table 1 for formal definitions.

The hybrid bitvector consists of the following three components:

1. 1.

   an array of hyperblock headers $A_H$,

2. 2.

   an array of superblock and block headers $A_S$, and

3. 3.

   an array of variable-sized block encodings $A_E$.

The $i$th hyperblock header gives context for the hyperblock ${\mathrm{hblock}}_B(i)$ and contains (1) ${\mathrm{hblockrank}}_{B,1}(i)$, and (2) ${\mathrm{hblockoffset}}_B(i)$.

The array $A_S$ contains both superblock headers and block headers. It is organized so that each superblock header is followed by the $k_s$ block headers for blocks inside that superblock. The $i$th superblock header gives context for ${\mathrm{sblock}}_B(i)$ and contains: (1) ${\mathrm{sblockrank}}_{B,1}(i)$, (2) ${\mathrm{sblockoffset}}_B(i)$, and (3) a flag indicating whether the superblock is uniform (i.e., it contains only zeroes or ones). The $i$th block header describes ${\mathrm{block}}_B(i)$ and contains: (1) ${\mathrm{blockones}}_B(i)$, (2) ${\mathrm{blockenclen}}_B(i)$, and (3) ${\mathrm{specialbit}}_B(i)$, a special bit that gives additional information about the encoding. The ${\mathrm{specialbit}}_B(i)$ is interpreted differently for each encoding. For the minority encoding, ${\mathrm{specialbit}}_B(i)$ identifies the minority bit. For the run-length encoding, it identifies the first bit of that block. For the plain encoding, it is ignored. Note that ${\mathrm{blockrank}}_{B,1}(i)$ and ${\mathrm{blockoffset}}_B(i)$ are not stored, but they can be computed as the sums of ${\mathrm{blockones}}_B(\cdot )$ and ${\mathrm{blockenclen}}_B(\cdot )$ over preceding blocks (in the same superblock).

Block encodings are concatenated to form the array $A_E$. The encoding for the $i$th block is located at offset ${\mathrm{hblockoffset}}_B(\lfloor \frac{i-1}{k_h}\rfloor +1)+{\mathrm{sblockoffset}}_B(\lfloor \frac{i-1}{k_s}\rfloor +1)+{\mathrm{blockoffset}}_B(i)$ with length ${\mathrm{blockenclen}}_B(i)$. The encoding type of the $i$th block can be identified from ${\mathrm{blockenclen}}_B(i)$ together with ${\mathrm{blockones}}_B(i)$. If ${\mathrm{blockenclen}}_B(i)=\frac{b}{8}$, then the block uses plain encoding. Otherwise, if ${\mathrm{blockenclen}}_B(i)=\min \{{\mathrm{blockones}}_B(i),b-{\mathrm{blockones}}_B(i)\}$, then the block is minority encoded. In all remaining cases, it is run-length encoded.

To save space, the run-length encoding in the hybrid bitvector does not list the last two run endings; instead, they can be recovered from the stored run endings together with the block headers. More specifically, suppose that the $i$th block in $B$ is run-length encoded, with all but the last two run endings stored as $(r_1,r_2,\mathrm{\dots },r_{m-2})$. That is, there are $m={\mathrm{blockenclen}}_B(i)+2$ maximal runs in ${\mathrm{block}}_B(i)$. On the other hand, we know $r_m=b$ and the set of run endings for runs containing 1-bits is $D=\{x\in [1..m]:(x+{\mathrm{specialbit}}_B(i))\text{ is even}\}$. Using all this information, we can compute $r_{m-1}$ by solving the equation ${\sum }_{d\in D}(r_d-r_{d-1})={\mathrm{blockones}}_B(i)$ (where $r_0=0$). Hence, we are able to recover the full run-length encoding $(r_1,r_2,\mathrm{\dots },r_m)$ from the stored run endings $(r_1,r_2,\mathrm{\dots },r_{m-2})$ and the block headers.

We use one parameter to control the space overhead of our select data structure. Let $\rho$ denote this parameter; in our implementation, we set $\rho =128$. Further, let $\tau$ denote the sampling period between consecutive sampled $c$-bits. We choose $\tau$ to be the smallest positive integer such that sampling every $\tau$th $c$-bit yields at most $\max \{\lfloor n/(64\rho )\rfloor ,2\}$ sampled positions. We store these samples in a lookup table $L_s$ as follows: for every integer $j\ge 0$ with , the entry $L_s[j+1]$ is the index of the superblock containing the $(j\tau +1)$th $c$-bit in $B$, and the final entry is a sentinel equal to $\lceil n/(k_{s}b)\rceil$, i.e., the index of the last superblock. Since each entry of $L_s$ is a 64-bit superblock index and the number of entries is bounded as above, the table uses about $n/\rho$ bits in practice.

To support select queries on the hybrid bitvector, we augment it with the following two components:

1. 1.

   the sampling period $\tau$, and

2. 2.

   the lookup table $L_s$.

To compute ${\mathrm{select}}_B(q,c)$, we proceed as follows:

1. 1.

   Identify the superblock. First, we use the array $L_s$ to narrow the search to a short interval of superblocks. We compute $u:=\lfloor (q-1)/\tau \rfloor +1$, $i_s^{\prime }:=L_s[u]$, and $i_s^{\prime \prime }:=L_s[u+1]$. By construction, the superblock containing the $q$th $c$-bit lies between these two indices, that is, $i_s^{\prime }\le i_s\le i_s^{\prime \prime }$. We then locate the exact superblock index $i_s$ by binary search in $[i_s^{\prime }..i_s^{\prime \prime }]$, where .

2. 2.

   Recover the superblock context. Once $i_s$ is known, the hyperblock containing it is immediate. Let $i_h=\lfloor \frac{k_s(i_s-1)}{k_h}\rfloor +1$. From the corresponding hyperblock and superblock headers, we obtain the number of $c$-bits preceding ${\mathrm{sblock}}_B(i_s)$, namely ${\mathrm{hblockrank}}_{B,c}(i_h)+{\mathrm{sblockrank}}_{B,c}(i_s)$, as well as the offset ${\mathrm{hblockoffset}}_B(i_h)+{\mathrm{sblockoffset}}_B(i_s)$ of the block encodings belonging to that superblock in $A_E$.

3. 3.

   Handle the uniform-superblock case. If the uniform-superblock flag is set, then every bit in ${\mathrm{sblock}}_B(i_s)$ is equal, and the answer is obtained immediately from the beginning of the superblock and the local offset of the queried occurrence inside it. In this case, the array $A_E$ is not accessed.

4. 4.

   Identify the block and the local query index. Otherwise, we scan the $k_s$ block headers that follow the superblock header in $A_S$ from left to right until we reach the block ${\mathrm{block}}_B(i_b)$ containing the $q$th $c$-bit. During this scan, we compute both ${\mathrm{blockrank}}_{B,c}(i_b)$ and ${\mathrm{blockoffset}}_B(i_b)$ as sums over the preceding blocks in the same superblock. We then define the local query index inside ${\mathrm{block}}_B(i_b)$ by $q^{\prime }=q-{\mathrm{hblockrank}}_{B,c}(i_h)-{\mathrm{sblockrank}}_{B,c}(i_s)-{\mathrm{blockrank}}_{B,c}(i_b)$. Thus, $q^{\prime }$ is the rank of the queried occurrence inside ${\mathrm{block}}_B(i_b)$, and the encoding of ${\mathrm{block}}_B(i_b)$ begins at offset ${\mathrm{hblockoffset}}_B(i_h)+{\mathrm{sblockoffset}}_B(i_s)+{\mathrm{blockoffset}}_B(i_b)$ in $A_E$.

5. 5.

   Answer the query inside the block. Let $B^{\prime }={\mathrm{block}}_B(i_b)$. We now compute ${\mathrm{select}}_{B^{\prime }}(q^{\prime },c)$ according to the encoding type of $B^{\prime }$:

   • $\mathrm{■}$

     If $B^{\prime }$ is minority encoded and $c={\mathrm{specialbit}}_B(i_b)$, then the block encoding already stores the positions of all $c$-bits in the block, so ${\mathrm{select}}_{B^{\prime }}(q^{\prime },c)$ is simply the $q^{\prime }$th stored position. Otherwise, the block encoding stores the positions of the opposite bit, and we scan these positions until we determine how many opposite bits occur before the $q^{\prime }$th $c$-bit; this lets us recover ${\mathrm{select}}_{B^{\prime }}(q^{\prime },c)$ from the corresponding gap.

   • $\mathrm{■}$

     If $B^{\prime }$ is plain encoded, we scan its 64-bit words from left to right, using hardware-supported bit-counting instructions to skip whole words until the answer lies in the current word, and then continue inside that word bit by bit.

   • $\mathrm{■}$

     If $B^{\prime }$ is run-length encoded and ${\mathrm{blockenclen}}_B(i_b)=0$, then the block contains at most two runs. In this case, ${\mathrm{select}}_{B^{\prime }}(q^{\prime },c)$ follows immediately from ${\mathrm{specialbit}}_B(i_b)$ and the length of the first run, which is determined by ${\mathrm{blockones}}_B(i_b)$. If $B^{\prime }$ is run-length encoded and ${\mathrm{blockenclen}}_B(i_b)>0$, we process the stored run endings from left to right. If the first run contains $c$-bits, we first check whether the answer already lies in that run. Afterwards, we inspect the stored run endings in pairs, each pair describing one run of $(1-c)$-bits followed by one run of $c$-bits. We subtract the lengths of whole $c$-runs until the queried occurrence falls into the current run. If all stored $c$-runs are exhausted, then the answer must lie in one of the last two runs, and its position is recovered using ${\mathrm{blockones}}_B(i_b)$ together with the fact that the last two run endings are omitted from the encoding.

6. 6.

   Return the position in $B$. Finally, we return $(i_b-1)b+{\mathrm{select}}_{B^{\prime }}(q^{\prime },c)$.

We conducted the experiments on an Intel Core i7-1355U CPU with 12 MiB L3 cache, 32 GiB of RAM, and 64-bit Ubuntu Linux 22.04.5 (kernel 6.8.0-60). Our code was compiled with g++ 11.4.0 using the flags -DNDEBUG -msse4.2 -funroll-loops -O3. We measured time using std::chrono::high_resolution_clock and the size of data structures via serialization.

As in [16], in our experiments we used datasets from the Pizza&Chili corpus [10], including both the standard (https://pizzachili.dcc.uchile.cl/texts.html) and the highly repetitive (https://pizzachili.dcc.uchile.cl/repcorpus.html) files. Basic statistics of all files are shown in Table 2.