Documentation Overview

Functionality

• Bit Vectors : BitVector
• Rank Data Structures : Rank, FlatRank, and WideRank
• Select Data Structures : RankSelect, FlatRankSelect, and WideRankSelect
• Configuration : See all options to configure the query algorithms and data structures

Examples

The code in this repository is very easy to use. To use our fastest implementation you can simply use the code below. If further tuning is required, we recommend to see the Configuration .

#include <pasta/bit_vector/bit_vector.hpp>
#include <pasta/bit_vector/support/flat_rank_select.hpp>
 
// Create a bit vector of size 1000 containing only zeros and flip every other bit.
pasta::BitVector bv(1000, 0);
for (size_t i = 0; i < bv.size(); ++i) {
  if (i % 2 == 0) {  bv[i] = 1; }
}
// Print the bit vector to see that everything worked ;-)
for (auto it = bv.begin(); it != bv.end(); ++it) {
  std::cout << ((*it == true) ? '1' : '0');
}
std::cout << std::endl;
 
// Create rank and select support and print the result of some queries.
pasta::FlatRankSelect rs(bv);
std::cout << rs.rank0(250) << ", " << rs.rank1(250)
          << ", "
          << rs.select0(250) << ", " << rs.rank1(250)
          << std::endl;

Benchmarks

Here, we present the most interesting results from our paper [1]. For more information on the hardware used and our competitors, please look to the paper where we explain the experiments in detail. Additionally, you can look at our repository that contains all scripts needed to reproduce the results.

First, we compare the additional space that is required for the rank and select data structures.

Next, we look at the query time for rank queries w.r.t. different fill counts of the bit vector.

Then, we look at select queries in the same setting.

Finally, we compare our own implementations that can be easily switched using the Configuration .