file.pdf (1.44 MB)
Download file

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

Download (1.44 MB)
journal contribution
posted on 01.01.1968, 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.

History

Publisher Statement

All Rights Reserved

Date

01/01/1968

Usage metrics

Exports