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[] and lower_bound methods.
• A succinct bitvector interface via the select and rank 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:

1. Using vector instructions (e.g. in la_vector::decode and ::lower_bound).
2. 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.