<p>I would try using a Bloom filter as your hash with the relation the same as your proposal. Computing the best filter size $m$ and number of hash functions $k$ for your application shouldn't be too hard; see Wikipedia's <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">Bloom Filter article</a> for inspiration. Depending on how badly you want to avoid false positives something like $m=64$ and $k=4$ might be enough.</p>

CC BY-SA 2.5
2010-09-29T22:31:23.310Z
For your application with very small sets you probably want $k$ quite large. This may be quite slow with the traditional approach. I instead suggest the following.
Warren Schudy
CC BY-SA 2.5
2010-09-29T22:54:50.333Z
(Continuation of previous comment) This is essentially a variation of Bloom filters. Assume you have three hash functions $h_1$, $h_2$, $h_3$ for the elements that produce $m$-bit strings. Hash an element to the bitwise and of these three. The resulting hashes will have about 1/8th 1s. Hash a set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will have in the nieghborhood of one-half ones, which will likely help keep the false positive rate down.
Warren Schudy
CC BY-SA 2.5
2010-09-29T22:58:09.490Z
The advantage of this variation is only that it makes better use of the parallelism inherent in the word operations that most computers have.
Warren Schudy
CC BY-SA 2.5
2010-09-29T23:35:23.000Z
Warren, you should post this as an answer. It deserves some votes
Suresh Venkat
CC BY-SA 2.5
2010-09-30T01:24:22.027Z
Suresh: reposted as answer at your suggestion.
Warren Schudy
CC BY-SA 2.5
2010-09-30T08:18:43.340Z
@Warren, @Suresh: I think it would make more sense to *combine* these two closely related answers, and then delete the comments. It would be easier to follow, in particular since one of the answers refers to parameters defined in the other.
Jukka Suomela
CC BY-SA 2.5
2010-09-29T22:03:21.513Z
2010-09-29T22:03:21.513Z
Warren Schudy
<p><em>(This answer was originally in comments but I'm moving it to a separate answer at Suresh's suggestion.)</em></p>

<p>For your application with very small sets you probably want the number of Bloom hash functions $k$ to be quite large to minimize the number of false positives. To save computation time I suggest the following variation of a Bloom filter. Assume you have three traditional hash functions $h_1$, $h_2$, $h_3$ for the elements that each produce $m$-bit strings. Hash each element to the bitwise and of these three hash functions. The resulting element hashes will be about $2^{-3}=1/8^{th}$ ones. Hash each set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will be in the neighborhood of one-half ones, which is presumably what you want to best keep the false positive rate down.</p>

<p>The difference between the above scheme are the traditional Bloom filter is analogous to the difference between the classic $G_{n,p}$ Erdos random graph model and random $d$-regular graphs. The above scheme has the effective number $k$ of Bloom hashes vary a bit around its mean of $m/8$ but $m/8$ is pretty large so this difference shouldn't matter.</p>

CC BY-SA 2.5
2010-09-30T10:11:35.503Z
This is particularly good for large m (32 or 64) as you suggested.
Alexandru
CC BY-SA 2.5
2010-09-30T01:23:29.220Z
2010-09-30T01:23:29.220Z
Warren Schudy
<p>I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be computed in linear time.</p>

<p>One example of H and R is:</p>

<ul>
<li>$H(A) = \bigvee_{x\in A}  1 &lt;&lt; (h(x) \mod k)$, where k is a fixed integer and h(x) a hash function over integers.</li>
<li>R(H(A), H(B)) = ((H(A) &amp; H(B)) == H(A))</li>
</ul>

<p>Are there any other good examples? (good is hard to define but intuitively if R(H(A), H(B)) then whp A is included in B).</p>

<p><strong>Later edit</strong>:</p>

<ol>
<li>I'm looking for a family of hash functions. I have many sets; 3 - 8 elements in each set; 90% of them have 3 or 4 elements. The example hash function I gave is not very well distributed for this case.</li>
<li>The number of bits of H(.) (in my example, k) which should be small (ie. H(.) must fit in an integer or long).</li>
<li>One nice property of R is that if H(.) has k bits then R(.,.) is true for (3^k - 2^k) / 4^k pairs, ie. for very few pairs.</li>
<li>Bloom filters are especially good for large sets. I tried using BF for this problem, but the optimum results were with only one function.</li>
</ol>

<p>(crosspost from <a href="https://stackoverflow.com/questions/3804100/hashing-sets-of-integers">stackoverflow</a>, I didn't receive an answer good enough)</p>

CC BY-SA 3.0
2013-10-09T19:26:31.613Z
@Alexandru: Do you know of any way to do this with the condition for R reversed? I mean such that if R(H(A), H(B)) then A is included in B.
Kim
CC BY-SA 2.5
2010-09-29T21:01:05.640Z
"whp" over what? Do you assume that your inputs come from a certain distribution?
Jukka Suomela
CC BY-SA 2.5
2010-09-29T21:02:14.747Z
And are you really looking for a single, fixed hash function and not a family of hash functions?
Jukka Suomela
CC BY-SA 2.5
2010-09-29T21:11:46.850Z
@Jukka: I think he means if R(H(A), H(B)), then with high probability we conclude that A is a subset of B. The probability is taken over random choices of A and B, as well as internal coin tosses of H and R (if any).
Sadeq Dousti
CC BY-SA 2.5
2010-09-29T21:22:58.993Z
I'm looking for a family of hash functions. My sets tend to be small (3 - 8 elements each; 90% of them have 3 or 4 elements) so the example hash function I gave is not very well distributed.
Alexandru
CC BY-SA 2.5
2010-09-29T21:32:07.127Z
One nice property of R is that if H(.) has n bits then R(.,.) is true for (3^n - 2^n) / 4^n pairs, ie. for very few pairs.
Alexandru
CC BY-SA 2.5
2010-09-29T21:32:37.747Z
Why doesn't an explicit bitmap work, given the size of the sets ? then the containment property is expressed as h(A) AND h(B) = h(A).
Suresh Venkat
CC BY-SA 2.5
2010-09-29T21:34:27.587Z
the size is small, but the values of the elements can be large.
Alexandru
CC BY-SA 2.5
2010-09-29T22:04:46.277Z
How badly do you need to avoid false positives? Is an occasional one OK or are they fatal?
Warren Schudy
CC BY-SA 2.5
2010-09-30T08:33:27.117Z
@Warren: False positives are ok.
Alexandru
CC BY-SA 2.5
2010-09-30T09:09:15.297Z
@Warren: I've given it more thought and I realized that I'm using the function in two ways:

1. k is small (8): I need good distribution, false positives are ok and unavoidable
2. k is large (32 or 64): false positives are bad, but not fatal (I can test the sets for inclusion).
Alexandru
CC BY-SA 2.5
2010-09-30T21:51:40.767Z
@Alexandru: I interpret your recent comment to mean that the space needed to store the hashes is problematic so you sometimes use 8-bit hashes. For the 8-bit hashes a bloom filter with a single hash function (i.e. your proposal) sounds hard to beat (but I don't have a proof). For the word-sized hashes I would use a Bloom filter with many hashes. Your recent edit indicated that you tried a Bloom filter and one function was optimal. Did you try the combination of a bloom filter with one function for the 8-bit hashes and with many functions for the 64-bit hashes?
Warren Schudy
CC BY-SA 2.5
2010-10-02T11:24:04.713Z
@Warren: I want to solver extremal sets to do sub summing of SAT clauses. Let me explain the algorithm. Each clause is hashed twice using an 8 bit hash (H1, R1) and another 64 bit hash (H2, R2). Then for each pair of 8-bit hashes which satisfy R1 I test all pair of sets with those hashes. The second hash is used to test for inclusion. So: first hash is used to reduce the number of set pairs to be checked for inclusion and therefore must have a good distribution; second is used to speed up testing and therefore must have a low false-positive rate.
Alexandru
CC BY-SA 2.5
2010-10-02T11:29:45.583Z
@Warren: (continuation) So far I use my example for 8bit hashes and your idea for 64bit hashes. It works great because the two hashes are independent which results in a small false positive rate (about 0.5%) when testing for inclusion. Nevertheless, I want to reduce the number of set pairs to test. Right now I test about 3% of the total number of pairs. Tweaking the integer hash function helps very little (<0.1%).

If anybody is interested I can publish some tests and a python program to measure the performance of the hash functions.
Alexandru
CC BY-SA 2.5
2010-10-03T18:55:49.423Z
Have you tried using larger hashes? That should reduce the number of false positives.
Warren Schudy
<ds.algorithms><hash-function>
Hashing sets of integers for inclusion testing
Alexandru
# Hashing sets of integers for inclusion testing

(Asked by: username_0 on 2010-09-29)

I'm looking for a hash function over sets H(.) and a relation R(.,.) such that if A is included in B then R(H(A), H(B)). Of course, R(.,.) must be easy to verify (constant time), and H(A) should be computed in linear time.

One example of H and R is:

* $H(A) = \bigvee\_{x\in A} 1 << (h(x) \mod k)$, where k is a fixed integer and h(x) a hash function over integers.
* R(H(A), H(B)) = ((H(A) & H(B)) == H(A))

Are there any other good examples? (good is hard to define but intuitively if R(H(A), H(B)) then whp A is included in B).

**Later edit**:

1. I'm looking for a family of hash functions. I have many sets; 3 - 8 elements in each set; 90% of them have 3 or 4 elements. The example hash function I gave is not very well distributed for this case.
2. The number of bits of H(.) (in my example, k) which should be small (ie. H(.) must fit in an integer or long).
3. One nice property of R is that if H(.) has k bits then R(.,.) is true for (3^k - 2^k) / 4^k pairs, ie. for very few pairs.
4. Bloom filters are especially good for large sets. I tried using BF for this problem, but the optimum results were with only one function.

(crosspost from [stackoverflow](https://stackoverflow.com/questions/3804100/hashing-sets-of-integers), I didn't receive an answer good enough)

**Tags:** ds.algorithms, hash-function
> **Comments:**
> **username_2**: "whp" over what? Do you assume that your inputs come from a certain distribution?  
> **username_2**: And are you really looking for a single, fixed hash function and not a family of hash functions?  
> **username_3**: @Jukka: I think he means if R(H(A), H(B)), then with high probability we conclude that A is a subset of B. The probability is taken over random choices of A and B, as well as internal coin tosses of H and R (if any).  
> **username_0**: I'm looking for a family of hash functions. My sets tend to be small (3 - 8 elements each; 90% of them have 3 or 4 elements) so the example hash function I gave is not very well distributed.  
> **username_0**: One nice property of R is that if H(.) has n bits then R(.,.) is true for (3^n - 2^n) / 4^n pairs, ie. for very few pairs.  
> **username_4**: Why doesn't an explicit bitmap work, given the size of the sets ? then the containment property is expressed as h(A) AND h(B) = h(A).  
> **username_0**: the size is small, but the values of the elements can be large.  
> **username_5**: How badly do you need to avoid false positives? Is an occasional one OK or are they fatal?  
> **username_0**: @Warren: False positives are ok.  
> **username_0**: @Warren: I've given it more thought and I realized that I'm using the function in two ways:  1. k is small (8): I need good distribution, false positives are ok and unavoidable 2. k is large (32 or 64): false positives are bad, but not fatal (I can test the sets for inclusion).  
> **username_5**: @Alexandru: I interpret your recent comment to mean that the space needed to store the hashes is problematic so you sometimes use 8-bit hashes. For the 8-bit hashes a bloom filter with a single hash function (i.e. your proposal) sounds hard to beat (but I don't have a proof). For the word-sized hashes I would use a Bloom filter with many hashes. Your recent edit indicated that you tried a Bloom filter and one function was optimal. Did you try the combination of a bloom filter with one function for the 8-bit hashes and with many functions for the 64-bit hashes?  
> **username_0**: @Warren: I want to solver extremal sets to do sub summing of SAT clauses. Let me explain the algorithm. Each clause is hashed twice using an 8 bit hash (H1, R1) and another 64 bit hash (H2, R2). Then for each pair of 8-bit hashes which satisfy R1 I test all pair of sets with those hashes. The second hash is used to test for inclusion. So: first hash is used to reduce the number of set pairs to be checked for inclusion and therefore must have a good distribution; second is used to speed up testing and therefore must have a low false-positive rate.  
> **username_0**: @Warren: (continuation) So far I use my example for 8bit hashes and your idea for 64bit hashes. It works great because the two hashes are independent which results in a small false positive rate (about 0.5%) when testing for inclusion. Nevertheless, I want to reduce the number of set pairs to test. Right now I test about 3% of the total number of pairs. Tweaking the integer hash function helps very little (<0.1%).  If anybody is interested I can publish some tests and a python program to measure the performance of the hash functions.  
> **username_5**: Have you tried using larger hashes? That should reduce the number of false positives.  
> **username_1**: @Alexandru: Do you know of any way to do this with the condition for R reversed? I mean such that if R(H(A), H(B)) then A is included in B.  

---

## 2 answers

### Answer by username_5 on 2010-09-30. Score: 10 | Accepted answer

*(This answer was originally in comments but I'm moving it to a separate answer at Suresh's suggestion.)*

For your application with very small sets you probably want the number of Bloom hash functions $k$ to be quite large to minimize the number of false positives. To save computation time I suggest the following variation of a Bloom filter. Assume you have three traditional hash functions $h\_1$, $h\_2$, $h\_3$ for the elements that each produce $m$-bit strings. Hash each element to the bitwise and of these three hash functions. The resulting element hashes will be about $2^{-3}=1/8^{th}$ ones. Hash each set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will be in the neighborhood of one-half ones, which is presumably what you want to best keep the false positive rate down.

The difference between the above scheme are the traditional Bloom filter is analogous to the difference between the classic $G\_{n,p}$ Erdos random graph model and random $d$-regular graphs. The above scheme has the effective number $k$ of Bloom hashes vary a bit around its mean of $m/8$ but $m/8$ is pretty large so this difference shouldn't matter.

> **Comments:**
> **username_0**: This is particularly good for large m (32 or 64) as you suggested.  

---

### Answer by username_5 on 2010-09-29. Score: 4

I would try using a Bloom filter as your hash with the relation the same as your proposal. Computing the best filter size $m$ and number of hash functions $k$ for your application shouldn't be too hard; see Wikipedia's [Bloom Filter article](http://en.wikipedia.org/wiki/Bloom_filter) for inspiration. Depending on how badly you want to avoid false positives something like $m=64$ and $k=4$ might be enough.

> **Comments:**
> **username_5**: For your application with very small sets you probably want $k$ quite large. This may be quite slow with the traditional approach. I instead suggest the following.  
> **username_5**: (Continuation of previous comment) This is essentially a variation of Bloom filters. Assume you have three hash functions $h_1$, $h_2$, $h_3$ for the elements that produce $m$-bit strings. Hash an element to the bitwise and of these three. The resulting hashes will have about 1/8th 1s. Hash a set to the bitwise or of the hashes of its constituent elements. Because your sets have 3-8 elements the resulting hashes will have in the nieghborhood of one-half ones, which will likely help keep the false positive rate down.  
> **username_5**: The advantage of this variation is only that it makes better use of the parallelism inherent in the word operations that most computers have.  
> **username_4**: Warren, you should post this as an answer. It deserves some votes  
> **username_5**: Suresh: reposted as answer at your suggestion.  
> **username_2**: @Warren, @Suresh: I think it would make more sense to *combine* these two closely related answers, and then delete the comments. It would be easier to follow, in particular since one of the answers refers to parameters defined in the other.  

---

