We consider the problem of computing information theoretic functions such as Entropy on a data stream, using sublinear space. Our first result deals with a measure we call the “entropy norm” of an input stream: it is closely related to entropy but is structurally similar to the well-studied notion of frequency moments. We give a polylogarithmic space one-pass algorithm for estimating this norm under certain conditions on the input stream. We also prove a lower bound that rules out such an algorithm if these conditions do not hold.…
Algorithms for computational problems on data streams have been the focus of plenty of recent research in several communities, such as theory, databases and networks [1, 5, 2, 12]. In this model of computation, the input is a stream of “items” that is too long to be stored completely in memory, and a typical problem involves computing some statistics on this stream. The main challenge is to design algorithms that are efficient not only in terms of running time, but also in terms of space (i.e., memory usage): sublinear space is mandatory and polylogarithmic space is often the goal.
~
A Parser has an input stream, a set of rules (generated from an extended **PEG**) that recognise input Structure and generate output structures, an output stream to collect generated output, and a current result (semantic value from the most recent Expression) that can be read and written within rules.