Adapting parallel algorithms to the W-Stream model, with applications to graph problems

In this paper we show how parallel algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the model. In this model, at each pass one input stream is read, one output stream is written, and data items have to be processed using limited space; streams are pipelined in such a way that the output stream produced at pass i is given as input stream at pass i+1. We first introduce a simulation technique that allows turning efficient algorithms into optimal ones, for many classical combinatorial problems, including list ranking and Euler tour of a tree. For other problems, most notably graph problems, however, this technique leads to suboptimal algorithms. To overcome this difficulty we introduce the Relaxed () computational model, as an intermediate model between and . allows every processor to access a non-constant number of memory cells per parallel round, albeit with some restrictions. The model, while being more powerful than the model, can be simulated in within the same asymptotic bounds. The extra power provided by allows us in many cases to substantially reduce the number of processors, while maintaining the same number of parallel rounds, leading to more efficient simulations of parallel algorithms. Our technique gives new insights on developing streaming algorithms and yields efficient algorithms for several classical problems in this model including sorting, connectivity, minimum spanning tree, biconnected components, and maximal independent set. In addition to allowing smooth space-passes tradeoffs, our algorithms are also shown, by proving almost-tight communication complexity-based lower bounds in , to be optimal up to polylog factors.