10
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ "whp" over what? Do you assume that your inputs come from a certain distribution? $\endgroup$ – Jukka Suomela Sep 29 '10 at 21:01
  • $\begingroup$ And are you really looking for a single, fixed hash function and not a family of hash functions? $\endgroup$ – Jukka Suomela Sep 29 '10 at 21:02
  • $\begingroup$ @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). $\endgroup$ – M.S. Dousti Sep 29 '10 at 21:11
  • $\begingroup$ 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. $\endgroup$ – Alexandru Sep 29 '10 at 21:22
  • $\begingroup$ 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. $\endgroup$ – Alexandru Sep 29 '10 at 21:32
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is particularly good for large m (32 or 64) as you suggested. $\endgroup$ – Alexandru Sep 30 '10 at 10:11
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Sep 29 '10 at 22:31
  • $\begingroup$ (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. $\endgroup$ – Warren Schudy Sep 29 '10 at 22:54
  • $\begingroup$ The advantage of this variation is only that it makes better use of the parallelism inherent in the word operations that most computers have. $\endgroup$ – Warren Schudy Sep 29 '10 at 22:58
  • $\begingroup$ Warren, you should post this as an answer. It deserves some votes $\endgroup$ – Suresh Venkat Sep 29 '10 at 23:35
  • 2
    $\begingroup$ @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. $\endgroup$ – Jukka Suomela Sep 30 '10 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.