Simpler algorithm for estimating frequency moments of data streams

被引：34

作者：

Bhuvanagiri, Lakshminath ^{[1
]}

Ganguly, Sumit ^{[1
]}

Kesh, Deepanjan ^{[1
]}

Saha, Chandan ^{[1
]}

机构：

[1] Indian Inst Technol, Kanpur 208016, Uttar Pradesh, India

来源：

PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 2006年

关键词：

D O I：

10.1145/1109557.1109634

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of estimating the eh frequency moment F(k) over a data stream by looking at the items exactly once as they arrive was posed in [1, 2]. A succession of algorithms have been proposed for this problem [1, 2, 6, 8, 7]. Recently, Indyk and Woodruff [11] have presented the first algorithm for estimating Fk, for k > 2, using space 0(71.1 -21) matching the space lower bound (up to poly-logarithmic factors) for this problem [1, 2, 3, 4, 13] (n is the number of distinct items occurring in the stream.) In this paper, we present a simpler 1-pass algorithm for estimating Fk.

引用

页码：708 / 713

页数：6

共 14 条

[1] The space complexity of approximating the frequency moments
Alon, N
Matias, Y
Szegedy, M
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (01) : 137 - 147
[2] [Anonymous], 1996, P 28 ANN ACM S THEOR
[3] BARYOSSEF Z, 2002, P 34 ACM S THEOR COM
[4] CHAKRABARTI A, 2003, P 18 ANN IEEE C COMP
[5] Charikar M., 2002, P 29 INT C AUT LANG
[6] COPPERSMITH D, 2004, P 15 ACM SIAM S DISC
[7] GANGULY S, P 8 INT WORKSH RAND
[8] GANGULY S, P INT C FDN IN PRESS
[9] GANGULY S, 2004, HYBRID TECHNIQ UNPUB
[10] INDYK P, 2005, P 37 ACM S THEOR COM

← 1 2 →