The value of multiple read/write streams for approximating frequency moments

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by such an algorithm. The other key parameters are the number of streams the algorithm uses and the number of passes it makes on these streams. We consider how the addition of these multiple read/write streams impacts the ability of algorithms to approximate the frequency moments of the input stream. We show that any randomized read/write stream algorithm with a fixed number of streams and a sublogarithmic number of passes that produces a constant factor approximation of the k-th frequency moment Fk of an input sequence of length of at most N from {1,...,N} requires space Ω(N 1−4/k−δ) for any δ> 0. For comparison, it is known that with a single read-only data stream there is a randomized constant-factor approximation for Fk using Õ(N1−2/k) space and that there is a deterministic algorithm computing Fk exactly using 3 read/write streams, O(log N) passes, and O(log N) space. Therefore, although the ability to manipulate multiple read/write streams can add substantial power to the data stream model, with a sub-logarithmic number of passes this does not significantly improve the ability to approximate higher frequency moments efficiently. Our lower bounds also apply to (1 + ɛ)-approximations of Fk for ɛ ≥ 1/N.