Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences
verfasst von : Dong Zhou, David G. Andersen, Michael Kaminsky
Erschienen in: Experimental Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Rank & select data structures are one of the fundamental building blocks for many modern
succinct 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.