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},{}
.