Set-Difference Entropy

Travis Gagie, Meng He, and Gonzalo Navarro

We propose a new measure of entropy for a set of sets, which is related to how much they differ from each other. We show how to build a data structure that stores a set of sets within this entropy measure, so that access, membership, predecessor and successor queries are supported in logarithmic time. In addition, we give a new MST-based construction algorithm of the entropy measure that outperforms standard ones.