Documents
Presentation Slides
Presentation Slides
Practical Implementations of Compressed RAM
- Citation Author(s):
- Submitted by:
- Seungbum Jo
- Last updated:
- 20 February 2023 - 7:52pm
- Document Type:
- Presentation Slides
- Document Year:
- 2023
- Event:
- Presenters:
- Wooyoung Park
- Paper Code:
- 243
- Categories:
- Keywords:
- Log in to post comments
Given a string S over an alphabet of size σ, we consider practical implementations of extended compressed RAM on S, which supports access, replace, insert, and delete operations on S while maintaining S in compressed form. In this paper, we proposed two implementations where each of them is based on the compressed RAM of Jansson et al. [ICALP 2012], and Grossi et al. [ICALP 2013], respectively. Experimental results show that our implementations support the operations efficiently while keeping the space proportional to the entropy of the input during the updates.