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.
%0 Journal Article
%1 cm
%A Cormode, Graham
%A Muthukrishnan, S.
%D 2004
%J LATIN 2004: Theoretical Informatics
%K data, sketching, stream
%P 29--38
%T An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
%X 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.
@article{cm,
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.},
added-at = {2008-04-30T12:59:47.000+0200},
author = {Cormode, Graham and Muthukrishnan, S.},
biburl = {https://www.bibsonomy.org/bibtex/20b4563a386592dcb5283e0df59270b64/kdubiq},
description = {KDubiq Blueprint},
interhash = {ef64dcc557687b5ed7253d354927542e},
intrahash = {0b4563a386592dcb5283e0df59270b64},
journal = {LATIN 2004: Theoretical Informatics},
keywords = {data, sketching, stream},
pages = {29--38},
priority = {2},
timestamp = {2008-04-30T12:59:56.000+0200},
title = {An Improved Data Stream Summary: The Count-Min Sketch and Its Applications},
year = 2004
}