Recently a problem rose to me I'm not really sure what topic it belongs to:
The origin is a "labeling application". There are n objects (say files etc., n abt. 1e6). And there are t properties/ labels (t abt. 1e3). Every of the n objects is assigned to some labels. No restriction. Simple.
Every subset of labels filters (AND) the objects. For some subsets of labels you will get a great amount of objects, but there is no label you can add which "divides" the resulting objects, as none of these objects is labelled by any other label than the ones already used for filter. (BTW: Empty set (for objects) is excluded).
Actually it happens only "by chance" that I trap into such situation. Very unsatisfying.
So I would like to identify a priori those subsets of all my labels which produce such situation. (Kind of closure, or clique, or ...?).
Afterwards order those subsets by number of found objects, so I can invent a new label for each subset, which divides the resulting objects.
It looks like a kind of balanced-tree problem. Or finding a "base" that produces good partitions. Or...?
I'm not good at that but I might think the problem could well be expressed in terms of set-theory (2 sets, a relation, special subset of the relation that fulfill the condition).
I searched this and that way, but none of the well-known problems/ algs seems to fit. (Still I'm no expert in set-theory or database).
I hope anyone has a hint for me?
If it is identified and should be NP complete (which I suspect), may there is an approx. alg./ heuristic...
Time and "some" thinking let the solution dawn to me.
The problem can be solved in O [n * t]. (The 2^t monster is gone...)
The biggest hurdle on it was the origin the problem came from - and the description in that context.
What I was actually searching for is all sets of objects with equal assigment to labels. After building a list of all (object, assigment) pairs the job is only to build the equivalence classes wrt assigment values. Just pick out the largest classes - la voilà!
Mathematically it still looks like a kind of "closure" to me.