|
Title |
Compact Data Structures for Collections of Sets |
|
Authors |
Jarno N. Alanko, Philip Bille, Inge Li Gortz, Gonzalo Navarro, Simon J. Puglisi |
|
Publication date |
2025 |
|
Abstract |
We define a new entropy measure L(S), called the containment entropy, for a set S of sets, which considers the fact that some sets can be contained in others. We show how to represent S within space close to L(S) 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. |
|
Pages |
article 6 |
