<p>Represent sets as <a href="http://en.wikipedia.org/wiki/Bit_array" rel="nofollow">Bit Sets</a>. Java has <a href="http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html" rel="nofollow">built-in</a> implementation. A is subset of B if A &amp; B = A. These operations on bit sets are fast (O(1) ).</p>

CC BY-SA 3.0
2013-10-28T02:43:19.997Z
Great suggestion.  How do you know these bitset operations are O(1) ? Where is that documented?
user1068636
CC BY-SA 3.0
2013-10-28T06:41:06.763Z
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
CC BY-SA 3.0
2013-10-27T18:19:37.990Z
2013-10-27T18:19:37.990Z
Alexei Kaigorodov
<p>For an approximate solution, <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">bloom filters</a> 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.</p>

CC BY-SA 3.0
2013-11-15T14:41:08.977Z
2013-11-15T14:41:08.977Z
kutschkem
<p>Here's one heuristic that might help in some practical situations:</p>

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

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-25T16:50:32.117Z
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
CC BY-SA 3.0
2013-10-25T05:59:40.223Z
2013-10-25T05:59:40.223Z
D.W.
<p>If I have a set S = {1,2,3,4,5} that represents a universe and the following subsets of S: </p>

<p>U1 = {1,2}</p>

<p>U2 = {3,4,5}</p>

<p>C1 = {3,5}</p>

<p>C2 = {2}</p>

<p>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.  </p>

<p>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 ? </p>

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

CC BY-SA 3.0
2013-10-25T05:53:56.713Z
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.
CC BY-SA 3.0
2013-10-25T16:51:33.090Z
I would allow for pre-processing.
user1068636
<set-theory>
How to construct a special data structure that allows for "fast" subset operation?
user1068636
# How to construct a special data structure that allows for "fast" subset operation?

(Asked by: username_0 on 2013-10-25)

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.

**Tags:** set-theory

> **Comments:**
> **username_1**: 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?  
> **username_0**: I would allow for pre-processing.  

---

## 3 answers

### Answer by username_2 on 2013-10-27. Score: 2 | Accepted answer

Represent sets as [Bit Sets](http://en.wikipedia.org/wiki/Bit_array). Java has [built-in](http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html) implementation. A is subset of B if A & B = A. These operations on bit sets are fast (O(1) ).

> **Comments:**
> **username_0**: Great suggestion.  How do you know these bitset operations are O(1) ? Where is that documented?  
> **username_2**: 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).  

---

### Answer by username_3 on 2013-11-15. Score: 1

For an approximate solution, [bloom filters](http://en.wikipedia.org/wiki/Bloom_filter) 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.


---

### Answer by username_1 on 2013-10-25. Score: 1

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.

> **Comments:**
> **username_0**: 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?  

---

