The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each element with those hash functions, and incrementing the frequencies of various slots in various tables. To estimate the frequency of an element, the Count-Min sketch applies the hash functions to those elements and takes the minimum value out of all the slots that are hashed to.

The original paper on the Count-Min Sketch mentions that the data structure requires pairwise independent hash functions in order to get the necessary guarantees on its expected performance. However, looking over the structure, I don't see why pairwise independence is necessary. Intuitively, I would think that all that would be required would be that the hash function be a universal hash function, since universal hash functions are hash functions with low probabilities of collisions. The analysis of the collision probabilities in the Count-Min Sketch looks remarkably similar to the analysis of collision probabilities in a chained hash table (which only requires a family of universal hash functions, not pairwise independent hash functions), and I can't spot the difference in the analyses.

Why is it necessary for the hash functions in the Count-Min Sketch to be pairwise independent?



You are right: universal hashing suffices. Pairwise independence, while stronger, is the usual method to construct a universal hash family. Also pairwise independence is contrasted in the paper with the 4-wise independence required by previous methods, such as the AMS sketch.

  • $\begingroup$ Can you expand on why this is sufficient? It seems to me that in the last line of the proof on page 7, they use the fact that $P[(\forall j \in [1,d]). x_j > a] = (P[x_j > a])^d$, which seems to rely on the $d$ hash functions having independent probabilities of collision. Is this property implied by universal hashing? $\endgroup$
    – usul
    Dec 9 '12 at 21:16
  • $\begingroup$ @usul universality is used in the first equation on p 7 (this equation is in fact the definition of universality). what you are saying is true not because of any property of the hash family used, it is simply a consequence of the fact that each of the $d$ hash functions are chosen independently from each other! $\endgroup$ Dec 9 '12 at 22:51
  • $\begingroup$ and universality is sufficient because the only property of the hash family ever used is the equation on top of p.7 and this is the defining property of a universal hash family $\endgroup$ Dec 9 '12 at 22:52
  • $\begingroup$ I think this comes down to an omission in the paper: Do we choose a set of $d$ independent hash functions uniformly at random, or do we select each hash function from the family independently and uniformly at random (with replacement)? It doesn't quite specify. I assumed the former, but if we assume the latter, then I agree the statement follows trivially. $\endgroup$
    – usul
    Dec 9 '12 at 23:51
  • 1
    $\begingroup$ The text by Mitzenmacher and Upfal, in describing a Count-Min filter (pgs 328-331) use only universal hash functions, not pairwise independence, and they choose their hash functions independently and uniformly at random. So your answer is certainly correct. $\endgroup$
    – usul
    Dec 9 '12 at 23:52

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.