Network Applications of Bloom Filters: A Survey. Andrei Broder and Michael Mitzenmacher. Internet Mathematics Volume 1, Number 4 (2003), 485-509.
"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."
Article from "Encyclopedia of Database Systems" on Count-Min Sketch Graham Cormode 09. 5 page summary of the sketch and its applications.
A survey of synopsis construction in data streams. Charu Aggarwal.
"Thus, the count-min sketch does seem to have a number of practical advantages in many scenarios."
Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Michael Mitzenmacher, Eli Upfal. Cambridge University Press, 2005.
Describes Count-Min sketch over pages 329--332
Internet Measurement: Infrastructure, Traffic and Applications. Mark Crovella, Bala Krishnamurthy. Wiley 2006.
Advanced statistical approaches for network anomaly detection. Christian Callegari. ICIMP 10 Tutorial.
Video explaining sketch data structures with emphasis on CM sketch Graham Cormode
Data Stream Algorithms. Lecture notes, Chapter 3. Amit Chakrabarti. Fall 09.
Probabilistic inequalities and CM sketch. John Byers. Fall 2007.