# 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!

## 1 Answer

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.

• 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
• 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 – Sasho Nikolov Dec 9 '12 at 22:52
• 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
• 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. – usul Dec 9 '12 at 23:52