0
$\begingroup$

I have a list of sets that I would like to sort into a partial order based on the subset relation.

In fact, I do not require the complete ordering, only the minimal elements.

If I am not mistaken, each minimal elements should define one separate component of the respective graph - and this component should be a meet-semilattice.

What would be the most convenient space and time efficient way to solve this problem? Perhaps there is a way that does not require to build the entire graph? Perhaps there is a known algorithm under a better terminology than what I have naively described above?

I am aware that the time and space requirements are underspecified above, but I would be happy about any suggestions, whether they are proven to be optimal or not...

Background: I am currently building an entire graph database that holds all the edges between the sets and then look for the nodes that have no generalizations, but this is quite complicated, slow and requires a lot of (disk) space. The list mentioned above contains roughly 100 million sets.

$\endgroup$
  • $\begingroup$ I'm not sure I understand what you mean by "the lower bounds". Are you looking to topologically sort the graph of that partial order? Are you looking to find all inclusion-minimal sets (i.e., each set $S$ such that no subset of $S$ is in your list), i.e., to find all source vertices in that graph? If this is a practical problem, can you give us any indication of a typical range of sizes for the sets and the size of the universe their elements comes from? Do you have any guess at how many minimal elements are likely to be present, i.e., how large the output is? $\endgroup$ – D.W. Jan 8 at 18:57
  • $\begingroup$ @D.W. Your confusion was justified. It seems that the correct term is 'minimal elements'... I guess one could also call them the 'greatest lower bounds' of their subsets. $\endgroup$ – Radio Controlled Jan 9 at 8:10
1
$\begingroup$

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output all of the minimal sets. The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is the number of minimal elements. Or, to put it another way, if each set contains $m$ elements, the running time will be approximately $O(n(k+\log n)m)$ basic steps.

Why sort by size? This is an optimization. The smallest set is guaranteed to be minimal (there is none of smaller cardinality in the list, so none of its subsets can be in the list), so size is a useful trick to identify a set that must surely be minimal.

Without sorting by size, the worst-case running time is likely to end up as $O(n^2)$ set comparisons (or $O(n^2 m)$ basic steps), which is worse when $k \ll n$.


Here is an optimized version of that algorithm. Let $M$ be a data structure that stores a set of sets, as a trie: for instance, the set $\{1,3,6,7\}$ corresponds to the word $1367$ and is stored in the trie accordingly. Initially, $M$ is empty. Repeat the following: take the next set $S$ from the list; check whether any set in $M$ is a subset of $S$; if not, insert $S$ into $M$; finally delete $S$ from the list (or advance your pointer to the next element in the list). The "check..." operation can be performed fairly efficiently using a recursive traversal of the trie. At the end, once you've gone through the entire list, output $M$.

The worst-case running time of the optimized algorithm remains the same. In practice the running time might be improved significantly, perhaps to as fast as $O(nm)$ basic steps in some cases if you are lucky (but don't count on it). You can try both and see which works better in practice on the kind of workloads you are dealing with.

$\endgroup$
  • $\begingroup$ I think above the line you describe the same algorithm as in my reference. In the lower version, I understand the list is treated as a stack, right? If there is no subset of S in M, you put S into M, but you still have S on top of the list/stack. I fai lto see how it proceeds from there... $\endgroup$ – Radio Controlled Jan 9 at 8:38
  • $\begingroup$ Also, I am not sure if you have thought through the suggestion of the trie, which is a tree, not a semilattice as it requires sequences, not sets. Essentially, I could build the entire partial order as a graph as I have done, but it has too much overhead and requires too much space. $\endgroup$ – Radio Controlled Jan 9 at 8:47
  • $\begingroup$ And I am also not sure that the sorting is beneficial, because both very specific and very general can be minimal elements, the probability depends on the data. $\endgroup$ – Radio Controlled Jan 9 at 10:01
  • $\begingroup$ @RadioControlled, I made some edits to address your feedback; see the edited answer. I didn't check carefully whether it is the same algorithm. It might be, except that I don't see anything about sorting in your answer. I explained in the edited answer why sorting is useful. I edited my optimized algorithm to clarify that S is always deleted. I did think through the use of a trie; I describe in my answer how to convert each set to a sequence, so that it can be stored in the trie. I hope this is helpful. $\endgroup$ – D.W. Jan 9 at 17:42
  • $\begingroup$ Do you realize that two elements can be incomparable? The smallest set is guaranteed to be minimal, but in general it cannot be said that small sets in M are more likely to be generalizations of the remaining larger sets in S. Consider that when you see sets first that are likely generalizations, then M is also larger when you get to the larger sets, meaning that you have to go through more sets in 'M' earlier - that is unless you are more likely to find a generalization of the set from 'S', but this again depends mostly on the data. $\endgroup$ – Radio Controlled Jan 10 at 12:12
0
$\begingroup$

I have found a solution in this paper, p.12.

The algorithm mentioned there as proof should translate to the following python code:

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

I expect the break to be crucial for actual runtime, so it might be good idea to sort X in advance to get early breaks -- but I am not sure about that.

Another point that I see here is that > is supposed to be irreflexive, so x>x does not hold. But for this code it would be better if it did. If a==x, it breaks instead of unnecessarily looking further.

UPDATE: I have now been able to test different implementations in Python. Please allow me to directly give the python code, I think it is sufficiently similar to Pseudocode -- and perhaps more concrete for many people.

Here is the implementation as taken from the paper:

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

Now this turned out to be too slow and we can already tell from the complexity that it is very bad if the width of the partial order, that is the number m of minimal elements is expected to be large.

The trick is to make this algorithm independent of m by avoiding going through all current minimal elements. Instead, we can make use of the fact that the lookup in the result set is fast (I guess this is where the trie comes into play).

For each x, we generate all generalizations. Now the complexity is dependent on the number of x and their size, but not so much on the number of minimal elements (only O(n log n)?). Even better, as we now have to remove non-minimal elements from the initial list of elements instead of adding them, the time used for each x is decreasing instead of increasing over runtime.

Here is the respective code:

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

This uses a generator function generalizations() to avoid computing more generalizations of x once one has already been found in the current minimal elements. This is already quite fast with my data, but it could perhaps be improved by generating generalizations first that are more general (it needs be tested if this makes it faster) and in particular by generating only generalizations that consist of elements that have already been observed in the current minimal elements. For example if our x is {a,b,c}, but no current minimal element has c in it, we do not have to generate any subset of x that contains c, i.e. only {a,b},{a},{b},{}.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.