Please use this identifier to cite or link to this item:
|Title:||Compressed bit vectors based on variable-to-fixed encodings|
Satti, Srinivasa Ra
|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.|
|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:
|parsed-bitvector.pdf||Post-review (final submitted author manuscript)||2.7 MB||Unknown||View/Open|
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.