Smaller RLZ-Compressed Suffix Arrays

Show full item record



Puglisi , S J & Zhukova , B 2021 , Smaller RLZ-Compressed Suffix Arrays . in A Bilgin , MW Marcellin , J SerraSagrista & JA Storer (eds) , 2021 DATA COMPRESSION CONFERENCE (DCC 2021) . IEEE Data Compression Conference , IEEE , pp. 213-222 , Data Compression Conference (DCC) , 23/03/2021 .

Title: Smaller RLZ-Compressed Suffix Arrays
Author: Puglisi, Simon J.; Zhukova, Bella
Editor: Bilgin, A; Marcellin, MW; SerraSagrista, J; Storer, JA
Contributor: University of Helsinki, Department of Computer Science
University of Helsinki, Department of Computer Science
Publisher: IEEE
Date: 2021
Language: eng
Number of pages: 10
Belongs to series: 2021 DATA COMPRESSION CONFERENCE (DCC 2021)
Belongs to series: IEEE Data Compression Conference
ISBN: 978-1-6654-0333-7
Abstract: 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 subarrays 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.
Subject: ACCESS
113 Computer and information sciences

Files in this item

Total number of downloads: Loading...

Files Size Format View
SimonPuglisi_paper.pdf 932.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record