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.
Represent sets as Bit Sets. Java has built-in implementation. A is subset of B if A &amp; B = A. These operations on bit sets are fast (O(1) ).