CRAM: Compressed Random Access Memory

Details CRAM: Compressed Random Access Memory CRAM: Compressed Random Access Memory

2010-11-08

arxiv.org/abs/1011.1708v2

Computer Science

Data Structures and Algorithms

Scientific paper

We present a new data structure called the \emph{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 \emph{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.

Affiliated with

Also associated with

No associations

Rating

CRAM: Compressed Random Access Memory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with CRAM: Compressed Random Access Memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CRAM: Compressed Random Access Memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-130712