expositions

Surveys

• • 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."

Coverage in Textbooks

• • 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.

Talks

• Slides from the original conference presentation

Tutorials:

• • Advanced statistical approaches for network anomaly detection. Christian Callegari. ICIMP 10 Tutorial.

  • Video explaining sketch data structures with emphasis on CM sketch Graham Cormode

Class Lectures:

• • Data Stream Algorithms. Lecture notes, Chapter 3. Amit Chakrabarti. Fall 09.

  • Probabilistic inequalities and CM sketch. John Byers. Fall 2007.

  • ppt slides, slides with examples,