2026-09-21T14:30:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26011 2026-09-05T19:34:20Z ddc:004 open_access

From Relative Compression to Hierarchical Compression Bille, Philip Gørtz, Inge Li Pérez-López, Máximo Relative compression RLZ string collections compressed representation data structures efficient algorithms We introduce a framework to use any relative compression algorithm as a subroutine for hierarchical relative compression. In a dataset consisting of n sequences, it consists of constructing a rooted tree on the sequences, using hashing and similarity techniques, and compressing the children of a node relative to their parent. We build up on previous techniques [Bille et al., 2023], and optimize them further for computational efficiency. We test our framework with three existing relative compression algorithms on six genomic datasets, and we show that in datasets that contain heterogeneous data, hierarchical relative compression improves the compression ratio by a factor 2 or more, when compared to relative compression to a single sequence. Apart from compression ratio, we also explore the trade-offs with respect to compression speed, dataset decompression speed, and average sequence decompression speed. With two of the surveyed algorithms, dataset decompression becomes faster and sequence decompression remains practical, at the cost of compression time, which remains competitive for the datasets with highest variability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Philip Bille and Inge Li Gørtz and Máximo Pérez-López 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.7 urn:nbn:de:0030-drops-260117 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode