{"ID":2867748,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.17819","arxiv_id":"2509.17819","title":"Theory Meets Practice for Bit Vectors Supporting Rank and Select","abstract":"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.","short_abstract":"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 st...","url_abs":"https://arxiv.org/abs/2509.17819","url_pdf":"https://arxiv.org/pdf/2509.17819v1","authors":"[\"Florian Kurpicz\",\"Niccolò Rigi-Luperti\",\"Peter Sanders\"]","published":"2025-09-22T14:14:25Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}