Compact Data Structures for Collections of Sets

Jarno N. Alanko, Philip Bille, Inge Li Gortz, Gonzalo Navarro, and Simon J. Puglisi

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.