Algorithm. Find the group of documents with the least amount of words

I need help with a problem which I have been working for the last month.

I have a group of documents, each document has a set of unique words (if the word appears more than once in the document, I count it only once). I want to find for a particular amount of documents the optimum group which contains the least amount of different words.

For example, if I have a set of five documents, each of them containing a set of words:

d1 = [ a , b, c, d, e ]
d2 = [ b , c, f ]
d3 = [ c , e, g ]
d4 = [ a , c, d ]
d5 = [ c , d, e ]

The set of three documents with the least amount of words would be (d1,d4,d5). This group of three documents would contain only a, b, c, d and e.

So far what I have tried is the "nearest neighbor" approach. Take the document with the least amount of new words. I extended it with a recursive limited brute force: take the next n documents with the least amount of new words.

Is there any better algorithm for finding a good set? I know the optimum set can only be solved by brute force, but that is obviously not doable here.

EDIT: Why I have the impression that "nearest neighbor" is a poor solution: By extending the set of documents I sometimes get a solution which is much worse than with less documents. Theoretically, the same set of documents could always be choosen independently of how many more new documents I add.

• I think you need to look at the number of differences between sets as a sort of distance, so basically the number of additions or removals from one set to become the other. If you look at it this way, worst case scenario is the size of set A and the size of set B means performing A.length + B.length operations. With this heuristic, you could probably immediately guarantee that some documents can be eliminated simply by sheer size. Then if you also knew what two sets have in common, you can make this more precise still by subtracting from A.length + B.length. Food for thought. – Neil Feb 8 at 10:20
• @Neil: unfortunately in my concrete example (real life documents) the size and amount of words among all documents is quite stable (I chose them to be). There are some documents with a similar set of words, but finding them would have o(n²) complexity. More challenging would be finding out which group of documents have similar sets of words, but the complexity by brute force is prohibitive. – julodnik Feb 8 at 12:46
• I would suppose the brute force approach would be implemented in a dynamic programming style: From N = 1 to (total number of unique words), Exhaustively enumerate all subsets of documents (the subset consisting of any number of documents) that has exactly N unique words when combined. This way, subsets that are the "leaders" (i.e. fewer uniques among the peers) will be enumerated earlier in the search. – rwong Apr 14 at 23:57