Estimating entropy and entropy norm on data streams

摘要: We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space. Our first result deals with measure we call “entropy norm” an input stream: it is closely related to but structurally similar well-studied notion frequency moments. give polylogarithmic space one-pass algorithm for estimating this norm under certain conditions stream. also prove lower bound that rules out if these do not hold. Our second group results are empirical present problem. For stream m items and given real parameter α, our uses $\tilde{O}(m^{2\alpha})$ provides approximation 1/α in worst case (1+e) “most” cases. then two-pass (1+e)-approximation algorithm. All algorithms quite simple.