The block-ε tree is a compressed rank/select dictionary that achieves new space-time trade-offs by exploiting the approximate linearity and the repetitiveness of the data. It is based on a combination of the LA-vector (paper, code) and the block tree (paper, code).
This is a header-only library. To compile the example, use the following commands:
git clone https://github.com/gvinciguerra/BlockEpsilonTree.git
cd BlockEpsilonTree
cmake . -DCMAKE_BUILD_TYPE=Release
make -j8This project is released for academic purposes under the terms of the GNU General Public License v3.0. Some methods implemented in this project are patent pending.
If you use this code for your research, please cite:
Paolo Ferragina, Giovanni Manzini, and Giorgio Vinciguerra. Repetition- and linearity-aware rank/select dictionaries. In: Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC), 2021.
@inproceedings{Ferragina:2021isaac,
author = {Ferragina, Paolo and Manzini, Giovanni and Vinciguerra, Giorgio},
booktitle = {Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC)},
title = {Repetition- and linearity-aware rank/select dictionaries},
year = {2021}}