A hybrid technique for estimating frequency moments over data streams

摘要: The problem of estimating the k frequency moment Fk, for any non-negative integral value k, over a data stream by looking at items exactly once as they arrive, was considered in seminal paper Alon, Matias and Szegedy [1, 2]. They present sampling based algorithm to estimate Fk where, ≥ 2, using space O(n1−1/k)). Coppersmith Kumar [7] [10], different methods, algorithms with complexity O(n1−1/(k−1)). In this paper, we an O(n1−2/(k+1)), > thereby, improving compared 7, 10] 4.