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
ML Engineer, PhD

Machine learning engineer with a strong background in mathematics and computer science.