parsed-bitvector.pdf (2.64 MB)
Compressed bit vectors based on variable-to-fixed encodings
journal contribution
posted on 2016-11-29, 11:01 authored by Seungbum Jo, Stelios Joannou, Daisuke Okanohara, Rajeev Raman, Srinivasa Ra SattiWe consider practical implementations of compressed bitvectors, which support rank and select
operations on a given bit-string, while storing the bit-string in compressed form. Our approach
relies on variable-to-fixed encodings of the bit-string, an approach that has not yet been considered
systematically for practical encodings of bitvectors. We show that this approach leads to fast
practical implementations with low redundancy (i.e., the space used by the bitvector in addition
to the compressed representation of the bit-string), and is a flexible and promising solution to
the problem of supporting rank and select on moderately compressible bit-strings, such as those
encountered in real-world applications.
History
Citation
The Computer Journal, 2016Author affiliation
/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer ScienceVersion
- AM (Accepted Manuscript)