Maintaining a set of smallest subsets

Question

Here are the operations that I'd like to perform on a hypothetical collection data structure that holds sets as its elements:

1. Insert a set into the data structure, but: (1) if the new set is a superset of any of the existing sets, don't add it (2) if the new set is a subset of any existing sets, remove them.
2. Enumerate all the sets currently in the collection

All the sets in question are subsets of a known finite set, say {0..10^4}.

Is there a way to do this efficiently?

Answer 1

Here is a recent paper on this problem: http://research.google.com/pubs/pub36974.html

Briefly, you cannot do much better than quadratic time in the worst case; but there are some tricks to speed it up in practice.