LA-vector is a compressed bitvector/container supporting efficient random access and rank queries. It uses novel ways of compressing and accessing data by learning and adapting to data regularities, as described in this research paper.
This repo provides a reference C++17 implementation of LA-vector with the following features:
- A container interface via the
operator[]
andlower_bound
methods. - A succinct bitvector interface via the
select
andrank
methods. - Navigation through iterators.
- Serialisation capabilities.
LA-vector is implemented in the two header files inside the include
directory, and it uses the sdsl library.
To compile sdsl, tests, and the example.cpp file, use the following commands:
git clone --recurse-submodules https://github.com/gvinciguerra/la_vector.git
cd la_vector
cmake . -DCMAKE_BUILD_TYPE=Release
make -j8
Contributions are welcome. Some ideas:
- Using vector instructions (e.g. in
la_vector::decode
and::lower_bound
). - Compressing segments and corrections.
This project is licensed under the terms of the Apache License 2.0.
If you use this code for your research, please cite:
Antonio Boffa, Paolo Ferragina, and Giorgio Vinciguerra. A “learned” approach to quicken and compress rank/select dictionaries. In Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX), 2021.
@inproceedings{Boffa:2021,
Author = {Boffa, Antonio and Ferragina, Paolo and Vinciguerra, Giorgio},
Booktitle = {Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)},
Title = {A ``learned'' approach to quicken and compress rank/select dictionaries},
Year = {2021}}
The code to reproduce the experiments of the paper is available here.