Carnegie Mellon University
file.pdf (1.44 MB)

Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences

Download (1.44 MB)
journal contribution
posted on 1968-01-01, 00:00 authored by Dong Zhou, David G. Andersen, Michael Kaminsky

Rank & select data structures are one of the fundamental building blocks for many modernsuccinct data structures. With the continued growth of massive-scale information services, the space efficiency of succinct data structures is becoming increasingly attractive in practice. In this paper, we re-examine the design of rank & select data structures from the bottom up, applying an architectural perspective to optimize their operation. We present our results in the form of a recipe for constructing space and time efficient rank & select data structures for a given hardware architecture. By adopting a cache-centric design approach, our rank & select structures impose space overhead as low as the most space-efficient, but slower, prior designs—only 3.2% and 0.39% extra space respectively—while offering performance competitive with the highest-performance prior designs.


Publisher Statement

All Rights Reserved



Usage metrics