Elias-Fano Compression for Space-Efficient Rank and Select Structures

Rank and select data structures support rank and select queries on bit vectors. Informally, a rank query counts the number of 1s or 0s in a bit vector, up to the $i$-th position, while a select query finds the position of the i-th 1 or 0. Efficient support for these data structures is important, due to their role in the design of a multitude of more sophisticated data structures. Examples include wavelet trees [7], as well as compressed suffix arrays and trees [8], commonly used for text indexing and in search engines. They have also been applied as a component in approximate membership query filters [15], which are utilized in numerous domains, including databases and computational biology. In sequences of monotonically non-decreasing integers compressed by the Elias-Fano encoding [2][3], select queries are necessary for efficient random access. Such sequences are found in inverted indexes, also commonly used in search engines [21].

In domains where rank and select data structures are utilized, memory is often at a premium. As such, in addition to query runtime, it is important to consider memory utilization when deciding which rank/select structure to use. One of the major challenges in the design of rank and select data structures is that reducing query time and reducing the memory footprint of the data structure are often at odds. Frequently, tradeoffs must be made in order to improve one or the other.

Performing rank and select efficiently requires an auxiliary data structure, otherwise a linear scan of the bit vector is required. The naïve approach of precomputing the results for all possible queries and storing these results in a fixed-width integer array is clearly very space-inefficient, with the space requirements of the new array dominating those of the original bit vector. Succinct data structures can store this auxiliary information much more compactly. Succinct data structures are those that require an amount of space close to the information-theoretic lower bound. If $M$ is the information-theoretical optimal number of bits needed to store some data, a succinct representation takes $M+o(M)$ bits of space.

While prior work has explored the design of theoretically optimal succinct rank and select data structures [19, 16], these are generally not practical, either due to high constant factors or a lack of regard for the realities of hardware architectures. For example, it has been observed and is now well-understood that cache-misses play a significant role in determining the runtime of rank and select queries [6]. As such, minimizing potential cache misses is an important design goal, and a challenge in the design of practical rank and select structures.

Practical rank and select structures do exist, and come with a wide variety of space and time tradeoffs. Because rank and select structures lend themselves particularly well to very large data sets and applications where memory usage is a bottleneck, in this work we focus primarily on the smallest of these structures, modifying their design to use even less memory. We work to preserve principled cache-centric design decisions made in prior work. The main contribution of this paper is the rank and select data structure, orzo, which saves space by making use of the aforementioned Elias-Fano encoding [2][3]. While this encoding is typically applied to very long sequences of integers, we instead leverage it at a very small “micro” scale, compressing many short spans of integers.

Informally, a rank query counts the number of 1s or 0s in a bit vector, up to the $i$-th position, while a select query finds the position of the i-th 1 or 0. Formally,¹¹1The literature varies on whether or not rank is defined as the count of bits up to, or up to and including the i-th bit. We use the former definition, as do the implementations against which we compare our approach. for a 0-indexed bit vector $B$ of length $n$:

For example, on the 0-indexed 10-bit vector 1011001101, $ran{k}_1(4)=3$ and $selec{t}_1(4)=6$. Mentions of rank and select in this paper are assumed to refer to $ran{k}_1$ and $selec{t}_1$; generalizing the techniques described to the $\alpha =0$ variants is straightforward.

We first discuss the design of rank-only data structures. Practical rank structures often follow a common general design pattern:

• $\mathrm{■}$

  Starting from a basic block of size $\ge 2$ bits, conceptualize a hierarchy of increasingly large sub-blocks of the bit vector. The largest block size is referred to as a super block (or upper block).

• $\mathrm{■}$

  Design a multi-layer indexing scheme to provide cumulative counts of one bits across different levels of blocks. The top layer, L0, has one index for each super block, and provides an absolute cumulative count of one bits up to the start of the corresponding block. The next layer, L1, provides cumulative counts up to the start of the next smallest block size, within a super block, and so on. Two or three layers typically works well in practice, with the middle blocks in a three-layer scheme often referred to as a lower blocks.

• $\mathrm{■}$

  Observe that as block size decreases, corresponding indices need fewer bits to store the cumulative sums within the block.

• $\mathrm{■}$

  When possible, further optimize the design of the data structure around minimizing cache misses. González [6] provides an extensive analysis of the effect that cache misses have on rank and select performance, concluding that they become an increasingly dominant part of the total query time as the size of the bit vector increases.

The size chosen for the basic block has a significant impact on the overall size of the rank and select data structure. The size of the basic block is inversely proportional to the size of the structure, but increasing the size of the basic block also results in longer query times.

cs-poppy and pasta-flat stand out as being the smallest practical rank and select data structures, and their design is extremely effective for minimizing cache-misses and achieving performance near that of much larger structures. For these reasons, we use them as a foundation from which we may consider various optimizations for space savings. There are two strategies by which we can approach reducing space requirements further:

1. 1.

   Increase the size of the basic block. As mentioned previously, the size of the basic block is inversely proportional to the size of the entire rank structure.

2. 2.

   Decrease the size of one of the layers. This could be achieved either by reducing the size of individual indices within a given layer, or by reducing the need for as many indices.

The first strategy is straightforward – we do not implement it in this work. The choice of a 512-wide basic block, as used by cs-poppy and pasta-flat, is empirically well-grounded. Zhou observes that for 512 bits, doubling the size of the basic block does not double the time it takes to popcount a block, whereas doubling beyond 512 does [20]. As the size of a cache line on modern processors is 64 bytes, we will never incur more than one cache miss in popcounting a basic block of 512 bits, and we allow more memory bandwidth to be free for other operations (assuming that the basic blocks are aligned to cache line boundaries). Although we do not experiment with a larger basic block, we do highlight that the design of orzo as described below should generalize to a hypothetical variant with a larger basic block.

The second strategy has different implications when applied to different layers in the rank structure. For example, decreasing the size of the L0 layer is likely to be far less effective in reducing the overall space requirements than reducing the size of the lower layers. Consider the space requirements in bytes of a rank data structure for an $N$-bit vector with super blocks of size $S{B}_{\mathrm{size}}$ bits, lower blocks of size $L{B}_{\mathrm{size}}$ bits, L0 indices of $L{0}_{\mathrm{bytes}}$, and L1-L2 indices of $L1L{2}_{\mathrm{bytes}}$:

For $S{B}_{\mathrm{size}}\gg L{B}_{\mathrm{size}}$ the right side of the sum is dominant. With $S{B}_{\mathrm{size}}=2^{44}$, $L{B}_{\mathrm{size}}=4096$, 64-bit L0 indices, and 128-bit L1-L2 indices in pasta-flat, this amounts to well under 0.01% of the total rank structure space, a negligible amount. If all else is kept equal, but the L1 index is reduced to be 20 bits wide (therefore supporting $S{B}_{\mathrm{size}}=2^{20}$), the larger L0 layer still consumes only $0.19\%$ of the full size of the rank structure.

Layers which consume more space are also more likely to be responsible for cache misses, as a smaller percentage of the layer is able to fit in various hardware caches. For example, the L0 layers in cs-poppy and pasta-flat can be cache-resident for even large bit vectors.

With this in mind, the L1-L2 layer is the clear choice to target for space saving optimizations. As previously described, cs-pasta and pasta-flat interleave an L1 index and several L2 indices into a single L1-L2 index. We want to avoid any approaches that involve splitting the indices, as an important goal in the design of orzo is to introduce as few additional cache misses as possible. At most, both of these structures will incur three cache misses in performing a rank query: one to access the L0 index, one to access the L1-L2 index, and one to access the underlying bit vector.

Compared to how rank queries are handled in pasta-flat, orzo introduces only one additional complication: the need to decode an L2 index. The L1 index is extracted in essentially the same way as pasta-flat (only the magnitude of the bit shift required changes), as is the L0 index (assuming the L0 index is necessary).

For decoding the L2 indices, the lower part of the Elias-Fano representation is easily extracted with a bit shift followed by a mask, in the same manner that full L2 indices are extracted from pasta-flat. The upper bits must be reconstructed. As discussed in Section 2.3, this requires computing $selec{t}_1(i)-i$ on the upper Elias-Fano bit vector. At only twenty bits wide, our upper bit vector fits within a machine word, so we can leverage fast in-word selection techniques. The best of these on x86-64 architectures [14] leverages two special instructions: PDEP and TZCNT. PDEP transfers bits from the first operand into a destination based on the mask in a second operand. TZCNT counts the number of trailing zero bits in the source and returns the count. For non-x86 architectures, broadword programming [9] provides a relatively efficient way to select within a word. The reconstructed upper bits are concatenated with the lower bits to construct the full L2 index. After decoding the L2 index and adding it to the L1 and L0 indices, the final step is to determine the number of ones present in the basic block, which we can do very quickly with a scan and popcount instructions (maximum of eight).

In order to speed up select operations, orzo samples the position of every 8192nd one bit, in the same fashion as cs-poppy and pasta-flat. This incurs a maximum additional space overhead of $0.39\%$ compared to the rank-only versions of these structures. Unfortunately, orzo’s design complicates select queries more than it does rank queries.

Recall that cs-poppy divides select samples into buckets, with one bucket per super block. For $select(y)$, the L0 layer is searched in order to find the super block in which the $y$-th one bit is present.³³3The cs-poppy paper describes a binary search, but the available implementation uses a linear scan. However, because of its narrower L1 index, orzo may have many more L0 entries; searching these would be costly; a scan would have to examine many elements, while a binary search would exhibit poor cache locality and would still visit substantially more entries than the equivalent in cs-poppy or pasta-flat.

To address this, we opt to introduce a second super block to orzo for select queries, and a corresponding second L0 layer, L0_select. Instead of covering $259072$ ($\approx 2^{18}$) bits, these select super blocks cover 4294895616 bits. This number is chosen instead of exactly $2^{32}$, as it is evenly divisible both by our regular super block size and our lower block size. The additional memory incurred by the second super block is negligible.

We can now scan our L0_select layer at the same speed as cs-poppy, and we can divide our select samples into fewer buckets. We obtain a select sample from our bucket in the same manner as cs-poppy, which locates a lower block near the target lower block containing the answer to our query. To find the lower block actually containing the answer, we must scan L1 indices.

orzo again complicates this by the fact that our L1 indices are only cumulative within our standard super blocks, not our select super blocks. While cs-poppy may simply examine the next L1 index and determine if the current block contains the solution to our query, orzo first needs to know the rank at the start of the regular super block that the current lower block is within. Luckily, this is simple to retrieve, as knowing what lower block we are in allows us to determine the regular L0 index corresponding to the start of our regular super block. We can now proceed with our scan of L1 indices until we reach the correct lower block. Our scan of L2 indices proceeds in a similar fashion to cs-poppy, with the exception that we must first decode the indices. Once the correct basic block is reached, we leverage the technique of using popcount instructions to find the correct word, and for select within a word we use the same PDEP and TZCNT instructions that we have already described, see Listing 1.

Although orzo does introduce some complications for select, its design does have one upside from a query performance perspective that helps offset some of the overhead from the extra bookkeeping. orzo’s lower blocks span 5632 bits, in contrast to pasta-flat’s 4096 bits. This means that it is sometimes the case that fewer L1 indices must be scanned in order to identify the correct lower block; this is especially true for sparser bit vectors.

All code for our orzo implementation, as well as the code for the implementations we compare against, was written in C++ and compiled with clang version 17.0.6. We performed our experiments on two different x86-64 processors from different vendors, provisioned on compute nodes running Red Hat Enterprise Linux (Version 8.10) through the University of Maryland’s Zaratan cluster. See Table 2 for the specifics of each platform. The CPUs supported different features (for example, no AVX512 on the AMD CPU), and we used different compiler flags for each CPU, see Table 3 for details. We always pin our benchmarking processes to CPU 1.

For our experiments, we mostly replicate the setups used by Zhou and Kurpicz in evaluating cs-poppy [20] and pasta-flat [11]. We create random bit vectors of various lengths at three different sparsity levels of one bits: 10%, 50%, and 90%. For each input we test ten million random queries, and we run all tests five times with randomized bit vectors. We show the average of these runs in our reported results (the deviation between runs is extremely small).

The following rank and select data structures are evaluated in our experiments:

• $\mathrm{■}$

  cs-poppy is Kurpicz’s [11] implementation of Zhou’s [20] data structure.⁴⁴4We opt to use Kurpicz’s implementation, as they demonstrate it to be faster than the original implementation, and Kurpicz reports that the original implementation has a bug that prevents select queries from terminating on large bit vectors.

• $\mathrm{■}$

  pasta-flat is Kurpicz’s [11] original version of the pasta-flat data structure.

• $\mathrm{■}$

  orzo is the rank and select data structure that we describe in Section 3.2, with ten Elias-Fano encoded L2 indices per interleaved L1-L2 index, and an L1 index size of 18 bits.

As the focus of this research is to improve the space efficiency of practical rank and select structures, we opt to compare only against structures which incur a space overhead of $\approx 3.51\%$ for rank and select, or $\approx 3.125\%$ for just rank. It is well-known that approaches which use more memory (and possibly make other tradeoffs as well, such as SPIDER’s [12] interleaving of the bit vector with the rank/select structure) can achieve better query times. Examples include pasta-wide, another rank structure by Kurpicz [11] which incurs an overhead of $10\%$, and rank9 by Vigna [17] which incurs an overhead of $25\%$. We also omit combined sampling [13] from our analysis, despite it meeting the specified space requirements. Zhou has demonstrated that it is considerably (2-3x depending on the size of the bit vector) less efficient for rank queries than cs-poppy, and slightly less efficient for select queries [20]. Additionally, combined sampling only supports bit vectors of up to $2^{32}$ bits.

For simplicity, in this section, we focus on orzo’s query performance relative only to pasta-flat. However, as can be seen in the performance plots in Figures 3 and 4, both pasta-flat and cs-poppy perform very similarly, so our observations apply to both. The performance plots annotate each data point for orzo with the percentage increase in query time over pasta-flat.

Query performance is generally quite consistent across different input sparsities, especially for rank, across both CPUs that we tested, and for all of the data structures. An exception is that for select, there is a jump in query time going from 50% sparse bit vectors to 90% sparse bit vectors. On the Xeon CPU, going from 50% to 90% sparsity for the $2^{34}$ input size increases query times from $\sim$156 ns (orzo) and $\sim$109 ns (pasta-flat) to $\sim$177 ns and $\sim$129 ns. See plots e and f of Figure 3. This is expected, because select queries must scan more L1 indices with decreasing density in the bit vector.

Relative performance between orzo and pasta-flat is not consistent across CPUs. For example, there is a $\sim$9% gap in query runtime between orzo and pasta-flat for rank queries on a $2^{34}$ bit vector using the Intel Xeon CPU. This becomes a $\sim$38% gap on the AMD EPYC. See corresponding a, b, and c plots of Figures 3 and 4. On the other hand, for select queries, the AMD EPYC ends up being the platform with less of a gap in query runtime at large input sizes.

While cs-poppy and pasta-flat are closer in performance to each other than orzo is to either, neither is consistently faster, with the winner varying across different query types, sparsities, and input sizes. This is in contrast to prior comparisons between these two data structures [11], which had pasta-flat consistently ahead.

The inconsistency across machines, input sizes, and sparsities implies that it is likely worth benchmarking different rank and select data structures on the hardware and input sizes with which they’re going to be used. While orzo might represent a good space/time tradeoff on one machine and one range of input sizes, this may not hold in other scenarios. The choice between the equally sized cs-poppy and pasta-flat structures is also less clear-cut than what prior research indicated, with cs-poppy actually having faster queries in many scenarios.

In this work, we examine several of the most space-efficient rank and select data structures. Using one of these as a foundation, we propose a scheme to achieve further compression by exploiting Elias-Fano encoding. Our data structure, orzo, realizes considerable space savings of $26.49\%$ over the rank components of cs-poppy and pasta-flat, achieving a new space/time tradeoff that is on the Pareto frontier of rank and select solutions. Our space savings do come at the cost of query time, but this is expected. We suggest that our solution is ideal for applications where memory is the primary bottleneck or a hard constraint, but fast rank and select queries are still necessary. As long as the query runtime is not the bottleneck in an application, the relative increases in query time are unlikely to be felt, due to the extremely small runtime of the queries in absolute terms. We also conjecture that our technique of using Elias-Fano encoding for micro-scale compression, as opposed to its typical use in compressing large datasets, might find use in the design and engineering of other data structures.