Zombit: Exploiting Runs in Bitvectors

ABSTRACT Introduction Bitvectors are a fundamental building block of many compact data structures. In this work, we propose a new compressed representation for bitvectors, named zombit‐vector , which compresses bitvectors with runs by splitting the bitvector into fixed‐length blocks and classifying them into three possible types depending on their content. Methods It supports the typical operations over bitvectors in time, but select in time. The total space required for this structure is bits. In addition, we introduce an extension pzombit‐vector where the blocks have variable length. The variable‐length partitioning adapts better to the distribution of the data, reducing space needs but requiring time for all operations. Results We include experiments on synthetic data and over two real‐world scenarios. The synthetic scenario shows the competitiveness of our techniques against well‐known state‐of‐the‐art alternatives. That experiment confirms that pzombit‐vector is able to use one‐tenth of zombit‐vector , but becomes 5 times slower. Our experiments with real applications demonstrate that the proposed techniques are practical and applicable in real‐world scenarios.