An improved data stream summary: The count-min sketch and its applications

被引：83
作者：
Cormode, G [1 ]
Muthukrishnan, S
机构：
[1] Rutgers State Univ, DIMACS, Piscataway, NJ 08854 USA
[2] Rutgers State Univ, Div Comp & Informat Syst, Piscataway, NJ 08854 USA
来源：
LATIN 2004: THEORETICAL INFORMATICS | 2004年 / 2976卷
基金：
美国国家科学基金会;
关键词：
D O I：
10.1007/978-3-540-24698-5_7
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 I/epsilon(2) to 1/epsilon in factor.
引用
收藏
页码：29 / 38
页数：10
相关论文
共 17 条
[1]   The space complexity of approximating the frequency moments [J].
Alon, N ;
Matias, Y ;
Szegedy, M .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (01) :137-147
[2]  
Alon N., 1999, Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, P10, DOI 10.1145/303976.303978
[3]  
Babcock B., 2002, Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), P1, DOI DOI 10.1145/543613.543615
[4]  
Charikar M., 2002, P 29 INT C AUT LANG, P693, DOI 10.1007/3-540-45465-9_59
[5]  
CORMODE G, 2004, P IEEE INF
[6]  
Cormode G., 2003, ACM Transactions on Database Systems (TODS), P296, DOI DOI 10.1145/1061318.1061325
[7]  
ESTAN C, P WORKSH MAN PROC DA
[8]   PROBABILISTIC COUNTING ALGORITHMS FOR DATABASE APPLICATIONS [J].
FLAJOLET, P ;
MARTIN, GN .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 31 (02) :182-209
[9]  
GAROFALAKIS M, 2002, P ACM SIGMOD INT C M
[10]  
GIBBONS P, 1999, DIMACS SERIES DISC A
12