count-min sketch & its applications
The Count-Min sketch is a simple technique to summarize large amounts of frequency data. It was introduced in 2003, and since then has inspired many applications, extensions and variations. This sitelet collects and explains this work on the Count-Min, or CM, sketch.
What is New?
Count-Min sketch paper wins the Imre Simon Test-of-Time award, 2014.
See last page, rightmost column, a use of Count-Min Sketch in CACM.
The Basics
G. Cormode and S. Muthukrishnan. Approximating data with the count-min data structure. IEEE Software, (2012). A general introduction to the sketch and its uses.
G. Cormode and S. Muthukrishnan. An improved data stream summary: The count-min sketch and its applications. LATIN 2004, J. Algorithm 55(1): 58-75 (2005) . The original paper (journal version) on the sketch.
G. Cormode and S. Muthukrishnan. Summarizing and mining skewed data streams. SDM 2005. Additional analysis of the sketch.