Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-31594-7_43
Title: CRAM: Compressed Random Access Memory
Authors: Jansson, J.
Sadakane, K.
Sung, W.-K. 
Issue Date: 2012
Source: Jansson, J.,Sadakane, K.,Sung, W.-K. (2012). CRAM: Compressed Random Access Memory. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7391 LNCS (PART 1) : 510-521. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-31594-7_43
Abstract: We present a new data structure called the Compressed Random Access Memory (CRAM) that can store a dynamic string T of characters, e.g., representing the memory of a computer, in compressed form while achieving asymptotically almost-optimal bounds (in terms of empirical entropy) on the compression ratio. It allows short substrings of T to be decompressed and retrieved efficiently and, significantly, characters at arbitrary positions of T to be modified quickly during execution without decompressing the entire string. This can be regarded as a new type of data compression that can update a compressed file directly. Moreover, at the cost of slightly increasing the time spent per operation, the CRAM can be extended to also support insertions and deletions. Our key observation that the empirical entropy of a string does not change much after a small change to the string, as well as our simple yet efficient method for maintaining an array of variable-length blocks under length modifications, may be useful for many other applications as well. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/78076
ISBN: 9783642315930
ISSN: 03029743
DOI: 10.1007/978-3-642-31594-7_43
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

11
checked on Feb 12, 2018

Page view(s)

31
checked on Feb 16, 2018

Google ScholarTM

Check

Altmetric


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