5
$\begingroup$

I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets.

A brute-force solution is to compare each set with all other sets and count the number of sets that are included in this set. Finally, pick the set with the highest count. This brute-force solution has a quadratic complexity and is very slow for my large number of sets. Is there a better solution with lower complexity?

$\endgroup$
  • 2
    $\begingroup$ What sort of metric are you using for "better?" Is it just complexity? I'm thinking Bloom Filters may be highly applicable here, but because they're a hashing solution, the worst-case complexity isn't much better, even though the average-case complexity is probably much better. $\endgroup$ – Cort Ammon Apr 5 '18 at 20:16
  • $\begingroup$ and quick check; your metric for the best set to pick is that it is the set which is a superclass of the largest number of other sets? $\endgroup$ – Cort Ammon Apr 5 '18 at 20:18
  • $\begingroup$ @CortAmmon Yes, that's exactly the metric I'm considering. I like to improve the runtime on my machine, so a solution with a better average-case complexity should work well. $\endgroup$ – Mahdi Apr 5 '18 at 20:44
  • 1
    $\begingroup$ The related problem of testing whether there exists any set that contains some other set (i.e., whether the answer is 1 or 0) is known as Subset Containment. This has been studied: see cstheory.stackexchange.com/q/37361/5038, cstheory.stackexchange.com/q/9896/5038. Perhaps you can apply similar ideas to your problem as well? Also related: cstheory.stackexchange.com/q/17404/5038, cs.stackexchange.com/q/75915/755. $\endgroup$ – D.W. Apr 5 '18 at 21:53
  • $\begingroup$ What is the size of those integers? $\endgroup$ – orlp Apr 7 '18 at 2:13
1
$\begingroup$

From the answer linked in D.W.'s comments, you wont be able to do this in less than quadratic time without more information. The problem you are trying to solve is more difficult than the Subset Containment problem, which is quadratic with the number of sets. We can, however, explore ways to make the average case better.

The first step is to identify if there is any pattern to the data which can be leveraged. For example, if the sets are random, then you can leverage that to find better runtimes with some partitioning tricks. If the values all happen to be less than 64, you could encode each set as a 64-bit numbers and do comparisons that way.

The most generic approach, however, is to try to minimize comparison time. The first step would be to sort the elements in each set. That makes it so you can always determine if one set is a subset of the other in linear time by scanning it.

Beyond that, you could look at bloom filters. A bloom filter is basically an array of bits, and each bit corresponds to the result of hashing the data differently. What is nice about bloom filters is that they allow you to combine values using OR logic. Use a bloom filter to hash each of the elements in a set, and OR the results together. Now it is easy to see that if you have a set $S_1$ and $S_2$ such that $S_1\subseteq S_2$ and you have their corresponding bloom filter arrays $B_1$ and $B_2$, then every bit in $B_1$ must also be set in $B_2$ (i.e. $B_2\land B_1=B_1$).

Thus, you will have to do $O(n^2)$ comparisons of the bloom filter arrays (which are bit-fields, so you can process them 32 or 64 bits at a time natively). If $B_i\land B_j=B_j$ for any $i, j$, then you have a potential subset. It's possible that you just had a bloom filter collision, so we have to test the arrays, which is linear with the size of each array.

Thus in the worst case, we don't save any time, but in the average case, we may be able to dramatically reduce the cost of comparing the sets.

There's a few more steps involved to make sure we don't saturate the bloom filters, but those can only be worked out when you know a little about the sizes of your sets, which I do not.

$\endgroup$
  • $\begingroup$ The size of each set is not known in advance. In some problems it may be less than 200, but in some problems around 1000 or even more. $\endgroup$ – Mahdi Apr 9 '18 at 6:36
  • 1
    $\begingroup$ So it's definitely beyond the scope of my answer, but analyzing the size of the sets would be O(n) time, so you may want to take some time to analyze them and pick the best ways to do the sorting. $\endgroup$ – Cort Ammon Apr 10 '18 at 17:48

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.