
Parallel Algorithms are Good for Streaming
Demetrescu, Camil; Escoffier, Bruno; Moruz, Gabriel; Ribichini, Andrea (2006), Parallel Algorithms are Good for Streaming. https://basepub.dauphine.fr/handle/123456789/6303
View/ Open
Type
Document de travail / Working paperDate
2006Publisher
Université Paris-Dauphine
Series title
Cahier du LAMSADESeries number
234Published in
Paris
Pages
16
Metadata
Show full item recordAbstract (EN)
In this paper we show how PRAM algorithms can be turned into efficient streaming algorithms for several classical combinatorial problems in the W-Stream model. In this model, at each pass one input stream is read and one output stream is written; streams are pipelined in such a way that the output stream produced at pass i is given as input stream at pass i +1. Our techniques yield near-optimal algorithms (up to polylog factors) for several classical problems in this model including sorting, connectivity, minimum spanning tree, biconnected components, and maximal independent set.Subjects / Keywords
W-stream model; combinatorial problems; streaming; PRAM algorithmsRelated items
Showing items related by title and author.
-
Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil; Ribichini, Andrea (2011) Article accepté pour publication ou publié
-
Ribichini, Andrea; Moruz, Gabriel; Escoffier, Bruno; Demetrescu, Camil (2007) Communication / Conférence
-
Correa, José; Dütting, Paul; Fischer, Felix; Schewior, Kevin; Ziliotto, Bruno (2021) Communication / Conférence
-
Maday, Yvon; Turinici, Gabriel (2002) Communication / Conférence
-
Maday, Yvon; Turinici, Gabriel (2003) Article accepté pour publication ou publié