Documents
Presentation Slides
Presentation Slides
Smaller RLZ-Compressed Suffix Arrays
- Citation Author(s):
- Submitted by:
- Bella Zhukova
- Last updated:
- 2 March 2021 - 2:38pm
- Document Type:
- Presentation Slides
- Event:
- Presenters:
- Bella Zhukova
- Categories:
- Log in to post comments
Recently it was shown (Puglisi and Zhukova, Proc. SPIRE, 2020) that the suffix array (SA) data structure can be effectively compressed with relative Lempel-Ziv (RLZ) dictionary compression in such a way that arbitrary subar- rays can be rapidly decompressed, thus facilitating compressed indexing. In this paper we describe optimizations to RLZ-compressed SAs, including generation of more effective dictionaries and compact encodings of index components, both of which reduce index size without adversely affecting subarray access speeds relative to other compressed indexes. Our experimental analysis also elucidates the relationship between subarray size and per element access time.