expositions

Surveys

"Cormode and Muthukrishnan devise the Count-Min Sketch, a variation of the Bloom filter designed to handle several problems on data streams… They are able to provide theoretical guarantees while using only pairwise independent hash functions; this is a significant advance, since pairwise indepenedent hash functions are generally easy to implement and quite efficient in practice."
"Thus, the count-min sketch does seem to have a number of practical advantages in many scenarios."

Coverage in Textbooks

Describes Count-Min sketch over pages 329--332
Comments