An improved data stream summary: The Count-Min Sketch and its applications

Graham Cormode

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We introduce a new sublinear space data structure - the Count-Min Sketch - for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point, range, and inner product queries to be approximately answered very quickly; in addition, it can be applied to solve several important problems in data streams such as finding quantiles, frequent items, etc. The time and space bounds we show for using the CM sketch to solve these problems significantly improve those previously known - typically from 1/ε2 to 1/ε in factor.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsMartin Farach-Colton
PublisherSpringer Verlag
Pages29-38
Number of pages10
Volume2976
ISBN (Print)3540212582, 9783540212584
DOIs
StatePublished - Jan 1 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2976

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'An improved data stream summary: The Count-Min Sketch and its applications'. Together they form a unique fingerprint.

  • Cite this

    Cormode, G. (2004). An improved data stream summary: The Count-Min Sketch and its applications. In M. Farach-Colton (Ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 2976, pp. 29-38). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2976). Springer Verlag. https://doi.org/10.1007/978-3-540-24698-5_7