Abstract (EN)

In this paper we show how parallel algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the View the MathML source 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 View the MathML source algorithms into optimal View the MathML source 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 View the MathML source (View the MathML source) computational model, as an intermediate model between View the MathML source and View the MathML source. View the MathML source allows every processor to access a non-constant number of memory cells per parallel round, albeit with some restrictions. The View the MathML source model, while being more powerful than the View the MathML source model, can be simulated in View the MathML source within the same asymptotic bounds. The extra power provided by View the MathML source allows us in many cases to substantially reduce the number of processors, while maintaining the same number of parallel rounds, leading to more efficient View the MathML source simulations of parallel algorithms. Our View the MathML source 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 View the MathML source, to be optimal up to polylog factors.