PUBLICATIONS

# A 'learned' approach to quicken and compress rank/select dictionaries

**Authors:** Antonio Boffa, Giorgio Vinviguerra, Paolo Ferragina.

**Abstract**

We address the well-known problem of designing, implementing and experimenting compressed data structures for supporting and queries over a dictionary of integers. This problem has been studied far and wide since the end of the ‘80s with tons of important theoretical and practical results. Following a recent line of research on the so-called learned data structures, we first show that this problem has a surprising connection with the geometry of a set of points in the Cartesian plane suitably derived from the input integers. We then build upon some classical results in computational geometry to introduce the first “learned” scheme for implementing a compressed rank/select dictionary. We prove theoretical bounds on its time and space performance both in the worst case and in the case of input distributions with finite mean and variance. We corroborate these theoretical results with a large set of experiments over datasets originating from a variety of sources and applications (Web, DNA sequencing, information retrieval and natural language processing), and we show that a carefully engineered version of our approach provides new interesting space-time trade-offs with respect to several well-established implementations of Elias-Fano, RRR-vector, and random-access vectors of Elias /-coded gaps.

**Type:** Conference paper

**Publication:** Proceedings of the SIAM Symposium on Algorithm Engineering and Experiments (ALENEX)

**Cite us:**

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}}
```