2026-07-22T12:48:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23805 2026-02-09T06:17:14Z ddc:004 open_access

Compact Data Structures for Collections of Sets Alanko, Jarno N. Bille, Philip Gørtz, Inge Li Navarro, Gonzalo Puglisi, Simon J. Compressed data structures entropy of sets data compression We define a new entropy measure L(𝒮), called the containment entropy, for a set 𝒮 of sets, which considers the fact that some sets can be contained in others. We show how to represent 𝒮 within space close to L(𝒮) so that any element of any set can be retrieved in logarithmic time. We extend the result to predecessor and successor queries and show how some common set operations can be implemented efficiently. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarno N. Alanko and Philip Bille and Inge Li Gørtz and Gonzalo Navarro and Simon J. Puglisi 2025 Is Part Of OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Grossi.6 urn:nbn:de:0030-drops-238051 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.6 eng https://creativecommons.org/licenses/by/4.0/legalcode