Why does the Count-Min Sketch require pairwise independent hash functions?

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?

Thanks!

• 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? – usul Dec 9 '12 at 21:16
• @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! – Sasho Nikolov Dec 9 '12 at 22:51
• 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. – usul Dec 9 '12 at 23:51