This paper answers that problem for sets (ordered by inclusion) and makes use of the sets' internal structure. Their idea is to build a forest encoding all the set by using a total ordering of the elements within the sets. So if you're working with sets of the natural numbers, you have a tree containing all the sets that have a 1 in them, a three with all the sets that have 2 (but not 1), etc. The trees corresponding the minimal elements of your ordering will probably be much more populated than their peers, unfortunately, so this could pose some performance problems.

I ran into a similar problem building a structure for anagram (and word subset/superset) search. If you convert each word to a 'signature' by sorting the letters, then a trie doesn't work as nicely any more--- the 'A' branch has tons of words and the 'W' branch has just a few. I should have just used a hash table since prefix searching on signatures isn't particularly meaningful.

However, this algorithm could still be very useful in a lot of problem domains where the typical set is a small fraction of the total number of elements. The Klee implementation uses it to cache known satisfiability problem instances, where each set contains just a few of the enormous universe of possible clauses. (Which is how I got here.)

For further followup: the references in http://cstheory.stackexchange.com/questions/8503/what-persistent-data-structure-for-a-set-of-partially-ordered-elements. The Daskalakis et al paper referenced there uses a representation that decomposes P into chains but from a quick skimming of the paper I'm not 100% sure how to build such decompositions.

## Error

Your reply will be screened

Your IP address will be recorded

You must follow the Privacy Policy and Google Terms of use.