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:
- 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.
- The number of bits of H(.) (in my example, k) which should be small (ie. H(.) must fit in an integer or long).
- 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.
- 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)