Please use this identifier to cite or link to this item:
Title: Compressed bit vectors based on variable-to-fixed encodings
Authors: Jo, Seungbum
Joannou, Stelios
Okanohara, Daisuke
Raman, Rajeev
Satti, Srinivasa Ra
First Published: 29-Dec-2016
Publisher: Oxford University Press (OUP), BCS, The Chartered Institute for IT
Citation: The Computer Journal, 2016
Abstract: 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.
DOI Link: 10.1093/comjnl/bxw103
ISSN: 0010-4620
eISSN: 1460-2067
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: Copyright © 2016, Oxford University Press (OUP), BCS, The Chartered Institute for IT. Deposited with reference to the publisher’s open access archiving policy.
Description: 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.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
parsed-bitvector.pdfPost-review (final submitted author manuscript)2.7 MBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.