Space-economical estimation of thepth frequency moments, defined asF_{p}= Σ_{i=1}^{n}|f_{i}|^{p}, forp> 0, are of interest in estimating all-pairs distances in a large data matrix, machine learning, and in data stream computation. Random sketches formed by the inner product of the frequency vectorf_{1}, ...,f_{n}with a suitably chosen random vector were pioneered by Alon, Matias and Szegedy, and have since played a central role in estimatingF_{p}and for data stream computations in general. The concept ofp-stable sketches formed by the inner product of the frequency vector with a random vector whose components are drawn from ap-stable distribution, was proposed by Indyk for estimatingF_{p}, for 0 <p< 2, and has been further studied by Li.In this paper, we consider the problem of estimating

F_{p}, for 0 <p< 2. A disadvantage of the stable sketches technique and its variants is that they requireO((1)/(ε^{2})) inner-products of the frequency vector with dense vectors of stable (or nearly stable) random variables to be maintained. This means that each stream update can be quite time-consuming. We present algorithms for estimatingF_{p}, for 0 <p< 2, that does not require the use of stable sketches or its approximations. Our technique is elementary in nature, in that, it uses simple randomization in conjunction with well-known summary structures for data streams, such as the CM sketch sketch and the Count sketch structure. Our algorithms require spaceO((1)/(ε^{2+p})) to estimateF_{p}to within 1 +/- ε factors and requires expected timeO(logF_{1}log (1)/(δ)) to process each update. Thus, our technique trades anO((1)/(ε^{p})) factor in space for much more efficient processing of stream updates. We also present a stand-alone iterative estimator forF_{1}.

*This file was generated by
bibtex2html 1.92.*