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?
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.
