Gómez-Brandón, Adrián2025-09-242025-09-242025-09-06A. Gómez-Brandón, "Zombit: Exploiting Runs in Bitvectors", Software: Practice and Experience, 2025, pp. 1–18, https://doi.org/10.1002/spe.700191097-024X0038-0644https://hdl.handle.net/2183/45808The data that support the findings of this study are openly available in zombit-vector at https://github.com/adriangbrandon/zombit-vector. Financiado para publicación en acceso aberto: Universidade da Coruña/CISUG[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 𝑂(1) time, but select in 𝑂(log 𝑛) time. The total space required for this structure is 𝑂(√𝑘𝑛) + 𝑜(√𝑘𝑛) bits. In addition, we introduce an extension pzombit-vector where the blocks have variablelength. The variable-length partitioning adapts better to the distribution of the data, reducing space needs but requiring 𝑂(log 𝑛) 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.engAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/bitvectorscompact data structuresbitvectors; compact data structures; compression; indicesindicesjournal articleopen access10.1002/spe.70019