Practical Dynamic Entropy-Compressed Bitvectors with Applications

Joshimar Córdova and Gonzalo Navarro

Compressed data structures provide the same functionality as their classical counterparts while using entropy-bounded space. While they have succeeded in a wide range of static structures, which do not undergo updates, they are less mature in the dynamic case, where the theory-versus-practice gap is wider. We implement compressed dynamic bitvectors B using |B|H0(B)+o(|B|) or |B|H0(B)(1+o(1)) bits of space, where H0 is the zero-order empirical entropy, and supporting queries and updates in O(w) time on a w-bit word machine. This is the first implementation that provably achieves compressed space and is also practical, operating within microseconds. Bitvectors are the basis of most compressed data structures; we explore applications to sequences and graphs.