Compressed Random Access Memory

Download Now Date Added: Nov 2010
Format: PDF

Motivated by applications which need to store huge amounts of data in the main memory of a computer, this paper proposes a new dynamic data-structure for compressed random access memory. Ferragina and Venturini recently gave a compressed data-structure for storing a string that allows substrings to be retrieved efficiently, but it requires the string to be static. Here, the authors extend their results in a non-trivial way to also allow the stored compressed string to be modified during execution.