Information-theoretic analysis of function computation on streams
Krishnamurthy Viswanathan · 2010
We consider the problem of determining the memory required to compute functions of data streams. A streaming system with memory constraint has to observe a collection of sources X1;X2;...;Xmsequentially, store synopses of the sources in memory, and compute a function of the sources based on the synopses. We are interested in the memory requirement, the number of bits of memory required to compute the function. In an earlier work, we established a correspondence between this problem and a functional source coding problem in cascade/line networks, and for the latter we derived inner and outer bounds on the rate region. In particular we showed that the outer bounds are achievable for all functions and a certain classes of distributions on the sources. In this paper we extend the class of distributions for which the outer bounds are achieved. By virtue of the correspondence between the two problems, this also characterizes the memory requirement for the associated streaming computation problem.