CRAM: Compressed Random Access Memory

Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

14 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages510-521
Number of pages12
EditionPART 1
DOIs
Publication statusPublished - 1 Dec 2012
Externally publishedYes
Event39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom
Duration: 9 Jul 201213 Jul 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7391 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period9/07/1213/07/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this