University of Leicester
Browse
parsed-bitvector.pdf (2.64 MB)

Compressed bit vectors based on variable-to-fixed encodings

Download (2.64 MB)
journal contribution
posted on 2016-11-29, 11:01 authored by Seungbum Jo, Stelios Joannou, Daisuke Okanohara, Rajeev Raman, Srinivasa Ra Satti
We 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, 2016

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Version

  • AM (Accepted Manuscript)

Published in

The Computer Journal

Publisher

Oxford University Press (OUP), BCS, The Chartered Institute for IT

issn

0010-4620

eissn

1460-2067

Acceptance date

2016-11-25

Copyright date

2016

Available date

2017-12-29

Publisher version

https://academic.oup.com/comjnl/article/doi/10.1093/comjnl/bxw103/2754558/Compressed-Bit-vectors-Based-on-Variable-to-Fixed

Notes

Also Conference Paper in Proceedings of the Data Compression Conference March 2014 DOI: 10.1109/DCC.2014.85;The file associated with this record is under embargo until 12 months after publication, in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC