Best way to find a subset of a set from a group of sets

Question

First, sorry for the ambiguous title.

Assume I have the following group of sets:

Group 1

s1 = ( x1, y1 )
s2 = ( x2 )

Group 2

m1 = ( x1, y1, y2 )
m2 = ( x1 )
m3 = ( x1 , x2 )

For each of the sets in Group 1 - call the set s, I need to find the sets in Group 2 - call it m - such that m is a subset of s.

So, for my example, the answer would be:

s1 -> m2
s2 -> nothing

For now, I'm storing the values in std:set, but I can change that if needed. Also, the sets can get big, so the algorithm needs to be efficient. For now I have a brute-force approach, which I'm not entirely satisfied with.

Any suggestions?

Answer 1

The first step would be to sort Group 1 according to cardinality (i.e. size). Then the algorithm is something on the order of:

foreach std::set M in "Group 2" {
  foreach std::set S in "Group 1" and S.size()>=M.size() {  // replace with binary search
     if ( std::includes(S.begin(),S.end(),M.begin(),M.end()) )
       { /* M is a subset of S */ }
    }
  }
}

This should have time complexity ~O(MSR), where M is the # of sets in "Group 2", S the # of sets in "Group 1", and R is the size of largest set in "Group #1".

Edit: It just occurred to me that it might be more efficient to use S.find() rather than calling std::includes() (which iterates sequentially) but I think that would only be true if M.size() is much smaller than S.size() -- O(M+S) vs O(MlogS).