Paper Info
Title
Simpler algorithm for estimating frequency moments of data streams
Abstract
The problem of estimating the kth frequency moment Fk 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 Õ(n1-2/k), 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.
Year
DOI
Venue
2006
10.1145/1109557.1109634
SODA
Keywords
Field
DocType
kth frequency moment fk,simpler algorithm,distinct item,data stream,simpler 1-pass algorithm,nucleolus,lower bound,np hard
Flow game,Discrete mathematics,Combinatorics,Frequency moments,Data stream mining,Data stream,Upper and lower bounds,Algorithm,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89871-605-5
59
2.10
References 
Authors
11
4
Name
Order
Citations
PageRank
Lakshminath Bhuvanagiri1642.93
Sumit Ganguly2813236.01
Deepanjan Kesh3746.53
Chandan Saha422716.91