Hashing sets of integers for inclusion testing

Question

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, I didn't receive an answer good enough)

Answer 1

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

Answer 2

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 for inspiration. Depending on how badly you want to avoid false positives something like $m=64$ and $k=4$ might be enough.