Engineering Select Support for Hybrid Bitvectors

One of the central problems in the design of compressed data structures is the efficient support for rank and select queries on bitvectors. These two operations form the backbone of more complex data structures (such as wavelet trees) used for the compact representation of texts, trees, graphs, or grids. Their efficient implementation is one of the most frequently studied problems in compressed data structures. One effective solution is the so-called hybrid bitvector implementation, which partitions the input bitvector into blocks and adaptively selects an encoding method, such as run-length, plain, or minority encoding, based on local redundancy. Experiments have shown that hybrid bitvectors achieve excellent all-around performance on repetitive and non-repetitive inputs. However, current implementations support only rank queries (i.e., counting the number of ones up to a given position) and lack support for select queries. This limitation significantly restricts their applicability. In this paper, we propose a method to add support for select queries to hybrid bitvectors, and we conduct an extensive set of experiments. Our results show that hybrid bitvectors offer excellent performance, matching the speed of the fastest and the space efficiency of the most compact existing bitvectors.