Compressed Hybrid Bit Vector Representations

A C++ library with hybrid schemes for representing bit vectors in compressed space. Provides the following bit vector representations:

  • bit_vector_stat (the fastest representation)
  • bit_vector_il
  • bit_vector_sd
  • bit_vector_rrr<block_size>
  • bit_vector_dyn (dynamic bit vector)
  • bit_vector_hyb
  • bit_vector_smart (the best speed vs. space trade-off)
  • bit_vector_small (the smallest representation)
  • bit_vector_smallrank

For a more detailed comparison, see benchmarks. The representations are based on the elementary rank/select dictionaries provided by the sdsl-lite and DYNAMIC libraries. The sdsl-lite library, in particular, was optimized to reduce RAM usage of SD bitmaps and improve speed of RRR representations.

Mikhail Karasikov
Mikhail Karasikov
PhD Student

My research interests include machine learning and bioinformatics.