# How to construct a special data structure that allows for “fast” subset operation?

If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S:

U1 = {1,2}

U2 = {3,4,5}

C1 = {3,5}

C2 = {2}

The above sets are guaranteed to be subsets of S, however they may not be subsets of each other. To check if C1 is subset of U2 I need to iterate through both sets and check if all elements of C1 are in U2. In this case 3 and 5 are elements of U2 thus C1 is a subset of U2.

But this operation is O(n) at best if you keep everything sorted. I'm wondering, is it possible to select the elements of S wisely or construct a data structure in such a way to perform fast (like O(1)) subset check operations ?

If this means I need to look into parallel algorithms I am open to that as well.

• I think you'll need to clarify. $O(1)$ time is not achievable unless you have a guarantee that all sets are of $O(1)$ size. In the worst case, the number of elements you'll have to examine is at least $\min(|C_i|,|U_j|)$, since you have to look at every element of the smaller set (in the worst case where it is a subset). Do you allow preprocessing of the sets? Do you need to answer many such subset queries? What's the application, and what are the requirements? – D.W. Oct 25 '13 at 5:53
• I would allow for pre-processing. – user1068636 Oct 25 '13 at 16:51

Represent sets as Bit Sets. Java has built-in implementation. A is subset of B if A & B = A. These operations on bit sets are fast (O(1) ).

• Great suggestion. How do you know these bitset operations are O(1) ? Where is that documented? – user1068636 Oct 28 '13 at 2:43
• I was wrong, O(1) only for small sets (no more than word size, 32 or 64), O(N) for larger sets, where N is the size of universe. Anyway, I belive it is the fastest way. And it can be parallelized, but effect is greater than overhead for only extremly large sets (millions of elements). – Alexei Kaigorodov Oct 28 '13 at 6:41

Here's one heuristic that might help in some practical situations:

Store the $U$ sets in sorted order, or for each $U$ set keep a hashtable of the elements of the set.

To test whether $C_i$ is a subset of $U_j$, select a few elements at random from $C_i$. For each selected element $x$, test whether $x \in U_j$. If $x \notin U_j$, you can immediately answer "No, $C_i$ is not a subset of $U_j$": you can answer the answer quickly. If $x \in U_j$ for each selected element, then there's no shortcut: you have to compare all the elements, for a running time of $O(|C_i| \lg |U_j|)$ or $O(|C_i|)$ (depending upon whether you have sorted lists or a hashtable).

This doesn't help if what you care about is worst-case performance. But if you have a practical application, depending upon how the sets you're dealing with are formed, you might find it helpful.

• If I have the control over the universe S - is it possible to achieve faster running times than what you state? I'm not an expert in math - but could this perhaps involve abstract algebra / group theory? – user1068636 Oct 25 '13 at 16:50

For an approximate solution, bloom filters could be an option. You get guaranteed negative answers, and a bound on the false positive rate. Bloom filters would have O(log(1/epsilon)) space complexity, where epsilon is the false positive rate you want. Time complexity for intersection would be the same. So compared to bit sets, you get a complexity that is, if i translate the false positive rate correctly, logarithmic in the universe's size, as compared to linear in that size for BitSets.