Estimating hybrid frequency moments of data streams

We consider the problem of estimating hybrid frequency moments of two dimensional data streams. In this model, data is viewed to be organized in a matrix form (A i,j )1≤i,j,≤n . The entries A i,j are updated coordinate‐wise, in arbitrary order and possibly multiple times. The updates include both increments and decrements to the current value of A i,j . The hybrid frequency moment F p,q (A) is defined as ${\sum }_{j=1}^n({\sum }_{i=1}^n{A_{i,j}}^p{)}^q$ and is a generalization of the frequency moment of one‐dimensional data streams. We present the first $\mathit{Õ}(1)$ space algorithm for the problem of estimating F p,q for p∈[0,2] and q∈[0,1] to within an approximation factor of 1±ϵ. The $\mathit{Õ}$ notation hides poly‐logarithmic factors in the size of the stream m, the matrix size n and polynomial factors of ϵ ^-1. We also present the first $\mathit{Õ}(n^{1‐1/q})$ space algorithm for estimating F p,q for p∈[0,2] and q?(1,2].