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?

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.

Other Expositions



Site Info