Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.17819 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909799655931904 |
|---|---|
| author | Kurpicz, Florian Rigi-Luperti, Niccolò Sanders, Peter |
| author_facet | Kurpicz, Florian Rigi-Luperti, Niccolò Sanders, Peter |
| contents | Bit vectors with support for fast rank and select are a fundamental building block for compressed data structures. We close a gap between theory and practice by analyzing an important part of the design space and experimentally evaluating a sweet spot. The result is the first implementation of a rank and select data structure for bit vectors with worst-case constant query time, good practical performance, and a space-overhead of just 0.78%, i.e., between $4.5\times$ and $64.1\times$ less than previous implementations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17819 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Theory Meets Practice for Bit Vectors Supporting Rank and Select Kurpicz, Florian Rigi-Luperti, Niccolò Sanders, Peter Data Structures and Algorithms Bit vectors with support for fast rank and select are a fundamental building block for compressed data structures. We close a gap between theory and practice by analyzing an important part of the design space and experimentally evaluating a sweet spot. The result is the first implementation of a rank and select data structure for bit vectors with worst-case constant query time, good practical performance, and a space-overhead of just 0.78%, i.e., between $4.5\times$ and $64.1\times$ less than previous implementations. |
| title | Theory Meets Practice for Bit Vectors Supporting Rank and Select |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.17819 |