TY - JOUR
T1 - An improved data stream summary
T2 - The count-min sketch and its applications
AU - Cormode, Graham
AU - Muthukrishnan, S.
N1 - Funding Information:
* Corresponding author. E-mail addresses: graham@dimacs.rutgers.edu (G. Cormode), muthu@cs.rutgers.edu (S. Muthukrishnan). 1 Supported by NSF ITR 0220280 and NSF EIA 02-05116. 2 Supported by NSF CCR 0087022, NSF ITR 0220280 and NSF EIA 02-05116.
PY - 2005/4
Y1 - 2005/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=14844367057&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=14844367057&partnerID=8YFLogxK
U2 - 10.1016/j.jalgor.2003.12.001
DO - 10.1016/j.jalgor.2003.12.001
M3 - Article
AN - SCOPUS:14844367057
SN - 0196-6774
VL - 55
SP - 58
EP - 75
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -