A two-dimensional stream is a sequence of coordinate-wise updates to a two-dimensional array (A_(i,j))_1≤i,j≤n. The hybrid frequency moments F_(p,q)(A) is denned as F_(p,q)(A) = ∑_(j=1)~n(∑_(i=1)~n|A_(ij)|~p)~q. For every 0 < ∈ < 1 and p,q ∈ [0, 2], we present an O(∈~(-6)poly(log n, log m,log(1/∈))) space algorithm for the problem of estimating F_(p,q), where, m is an upper bound on max_(i,j)|A_(i,j)|.
展开▼
