Adapting Parallel Algorithms to the W Stream
Model with Applications to Graph Problems 1st
Edition by Camil Demetrescu, Bruno Escoffier,
Gabriel Moruz, Andrea Ribichini ISBN
9783540744566 pdf download
https://ebookball.com/product/adapting-parallel-algorithms-to-
the-w-stream-model-with-applications-to-graph-problems-1st-
edition-by-camil-demetrescu-bruno-escoffier-gabriel-moruz-andrea-
ribichini-isbn-9783540744566-12246/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Introduction to Parallel Processing Algorithms and Architectures 1st
Edition by Behrooz Parhami ISBN 9780306469640 0306469642
https://ebookball.com/product/introduction-to-parallel-
processing-algorithms-and-architectures-1st-edition-by-behrooz-
parhami-isbn-9780306469640-0306469642-19872/
Conceptual Model Based Problem Solving Teach Students With Learning
Difficulties to Solve Math Problems 1st Edition by Yan Ping Xin
9462091048 9789462091047
https://ebookball.com/product/conceptual-model-based-problem-
solving-teach-students-with-learning-difficulties-to-solve-math-
problems-1st-edition-by-yan-ping-
xin-9462091048-9789462091047-17332/
Graph theory combinatorics and algorithms interdisciplinary
applications 1st Edition by Martin Charles Golumbic, Irith Ben Arroyo
Hartman ISBN 9780387250366 0387250360
https://ebookball.com/product/graph-theory-combinatorics-and-
algorithms-interdisciplinary-applications-1st-edition-by-martin-
charles-golumbic-irith-ben-arroyo-hartman-
isbn-9780387250366-0387250360-19882/
Data Structures and Algorithms with Object Oriented Design Patterns in
Java 1st Edition by Bruno Preiss, PEng ISBN 0471346136 9780471346135
https://ebookball.com/product/data-structures-and-algorithms-
with-object-oriented-design-patterns-in-java-1st-edition-by-
bruno-preiss-peng-isbn-0471346136-9780471346135-19836/
,An Introduction to Malliavin Calculus with Applications to Economics
1st Edition by Bernt Øksendal
https://ebookball.com/product/an-introduction-to-malliavin-
calculus-with-applications-to-economics-1st-edition-by-bernt-a-
ksendal-19340/
Self organising Map Techniques for Graph Data Applications to
Clustering of XML Documents 1st Edition by Tsoi, Hagenbuchner,
Sperduti 9783540370253
https://ebookball.com/product/self-organising-map-techniques-for-
graph-data-applications-to-clustering-of-xml-documents-1st-
edition-by-tsoi-hagenbuchner-sperduti-9783540370253-14488/
BSmart A Tool for the Development of Java Card Applications with the B
Method 1st edition by David Deharbe, Bruno Gomes, Anamaria Moreira
ISBN 3540876021 9783540876021
https://ebookball.com/product/bsmart-a-tool-for-the-development-
of-java-card-applications-with-the-b-method-1st-edition-by-david-
deharbe-bruno-gomes-anamaria-moreira-
isbn-3540876021-9783540876021-11366/
Discrete Mathematics and Its Applications With Combinatorics and Graph
Theory 7th Edition by Kenneth Rosen 0070681880 9780070681880
https://ebookball.com/product/discrete-mathematics-and-its-
applications-with-combinatorics-and-graph-theory-7th-edition-by-
kenneth-rosen-0070681880-9780070681880-17214/
Graph Transformations and Model Driven Engineering Essays Dedicated to
Manfred Nagl on the Occasion of his 65th Birthday 1st Edition by
Gregor Engels, Claus Lewerentz, Wilhelm Schafer, Andy Schurr, Bernhard
Westfechtel ISBN 3642173225 9783642173226
https://ebookball.com/product/graph-transformations-and-model-
driven-engineering-essays-dedicated-to-manfred-nagl-on-the-
occasion-of-his-65th-birthday-1st-edition-by-gregor-engels-claus-
lewerentz-wilhelm-schafer-andy-schurr-bernha/
, Adapting Parallel Algorithms to the W-Stream
Model, with Applications to Graph Problems
Camil Demetrescu1 , Bruno Escoffier2, Gabriel Moruz3 , and Andrea Ribichini1
1
Dipartimento di Informatica e Sistemistica,
Università di Roma “La Sapienza”, Rome, Italy
{demetres,ribichini}@dis.uniroma1.it
2
Lamsade, Université Paris Dauphine, France
3
MADALGO, BRICS, Department of Computer Science,
University of Aarhus, Denmark
Abstract. In this paper we show how parallel 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 give new insights on devel-
oping streaming algorithms and yield optimal algorithms (up to polylog
factors) for several classical problems in this model including sorting, con-
nectivity, minimum spanning tree, biconnected components, and
maximal independent set.
1 Introduction
Data stream processing has gained increasing popularity in the last few years
as an effective paradigm for processing massive data sets. Huge data streams
arise in several modern applications, including database systems, IP traffic anal-
ysis, sensor networks, and transaction logs [13, 23]. Streaming is an effective
paradigm also in scenarios where the input data is not necessarily represented
as a data stream. Due to high sequential access rates of modern disks, streaming
algorithms can be effectively deployed for processing massive files on secondary
storage [14], providing new insights into the solution of computational problems
in external memory. In the classical read-only streaming model, algorithms are
constrained to access the input data sequentially in one (or few) passes, using
only a small amount of working memory, typically much smaller than the input
size [14, 18, 19]. Usual parameters of the model are the working memory size s
and the number of passes p that are performed over the data, which are usually
Supported in part by the Sixth Framework Programme of the EU under contract
number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”),
and by the Italian MIUR Project “MAINSTREAM: Algorithms for massive infor-
mation structures and data streams”.
L. Kučera and A. Kučera (Eds.): MFCS 2007, LNCS 4708, pp. 194–205, 2007.
c Springer-Verlag Berlin Heidelberg 2007
Model with Applications to Graph Problems 1st
Edition by Camil Demetrescu, Bruno Escoffier,
Gabriel Moruz, Andrea Ribichini ISBN
9783540744566 pdf download
https://ebookball.com/product/adapting-parallel-algorithms-to-
the-w-stream-model-with-applications-to-graph-problems-1st-
edition-by-camil-demetrescu-bruno-escoffier-gabriel-moruz-andrea-
ribichini-isbn-9783540744566-12246/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
Introduction to Parallel Processing Algorithms and Architectures 1st
Edition by Behrooz Parhami ISBN 9780306469640 0306469642
https://ebookball.com/product/introduction-to-parallel-
processing-algorithms-and-architectures-1st-edition-by-behrooz-
parhami-isbn-9780306469640-0306469642-19872/
Conceptual Model Based Problem Solving Teach Students With Learning
Difficulties to Solve Math Problems 1st Edition by Yan Ping Xin
9462091048 9789462091047
https://ebookball.com/product/conceptual-model-based-problem-
solving-teach-students-with-learning-difficulties-to-solve-math-
problems-1st-edition-by-yan-ping-
xin-9462091048-9789462091047-17332/
Graph theory combinatorics and algorithms interdisciplinary
applications 1st Edition by Martin Charles Golumbic, Irith Ben Arroyo
Hartman ISBN 9780387250366 0387250360
https://ebookball.com/product/graph-theory-combinatorics-and-
algorithms-interdisciplinary-applications-1st-edition-by-martin-
charles-golumbic-irith-ben-arroyo-hartman-
isbn-9780387250366-0387250360-19882/
Data Structures and Algorithms with Object Oriented Design Patterns in
Java 1st Edition by Bruno Preiss, PEng ISBN 0471346136 9780471346135
https://ebookball.com/product/data-structures-and-algorithms-
with-object-oriented-design-patterns-in-java-1st-edition-by-
bruno-preiss-peng-isbn-0471346136-9780471346135-19836/
,An Introduction to Malliavin Calculus with Applications to Economics
1st Edition by Bernt Øksendal
https://ebookball.com/product/an-introduction-to-malliavin-
calculus-with-applications-to-economics-1st-edition-by-bernt-a-
ksendal-19340/
Self organising Map Techniques for Graph Data Applications to
Clustering of XML Documents 1st Edition by Tsoi, Hagenbuchner,
Sperduti 9783540370253
https://ebookball.com/product/self-organising-map-techniques-for-
graph-data-applications-to-clustering-of-xml-documents-1st-
edition-by-tsoi-hagenbuchner-sperduti-9783540370253-14488/
BSmart A Tool for the Development of Java Card Applications with the B
Method 1st edition by David Deharbe, Bruno Gomes, Anamaria Moreira
ISBN 3540876021 9783540876021
https://ebookball.com/product/bsmart-a-tool-for-the-development-
of-java-card-applications-with-the-b-method-1st-edition-by-david-
deharbe-bruno-gomes-anamaria-moreira-
isbn-3540876021-9783540876021-11366/
Discrete Mathematics and Its Applications With Combinatorics and Graph
Theory 7th Edition by Kenneth Rosen 0070681880 9780070681880
https://ebookball.com/product/discrete-mathematics-and-its-
applications-with-combinatorics-and-graph-theory-7th-edition-by-
kenneth-rosen-0070681880-9780070681880-17214/
Graph Transformations and Model Driven Engineering Essays Dedicated to
Manfred Nagl on the Occasion of his 65th Birthday 1st Edition by
Gregor Engels, Claus Lewerentz, Wilhelm Schafer, Andy Schurr, Bernhard
Westfechtel ISBN 3642173225 9783642173226
https://ebookball.com/product/graph-transformations-and-model-
driven-engineering-essays-dedicated-to-manfred-nagl-on-the-
occasion-of-his-65th-birthday-1st-edition-by-gregor-engels-claus-
lewerentz-wilhelm-schafer-andy-schurr-bernha/
, Adapting Parallel Algorithms to the W-Stream
Model, with Applications to Graph Problems
Camil Demetrescu1 , Bruno Escoffier2, Gabriel Moruz3 , and Andrea Ribichini1
1
Dipartimento di Informatica e Sistemistica,
Università di Roma “La Sapienza”, Rome, Italy
{demetres,ribichini}@dis.uniroma1.it
2
Lamsade, Université Paris Dauphine, France
3
MADALGO, BRICS, Department of Computer Science,
University of Aarhus, Denmark
Abstract. In this paper we show how parallel 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 give new insights on devel-
oping streaming algorithms and yield optimal algorithms (up to polylog
factors) for several classical problems in this model including sorting, con-
nectivity, minimum spanning tree, biconnected components, and
maximal independent set.
1 Introduction
Data stream processing has gained increasing popularity in the last few years
as an effective paradigm for processing massive data sets. Huge data streams
arise in several modern applications, including database systems, IP traffic anal-
ysis, sensor networks, and transaction logs [13, 23]. Streaming is an effective
paradigm also in scenarios where the input data is not necessarily represented
as a data stream. Due to high sequential access rates of modern disks, streaming
algorithms can be effectively deployed for processing massive files on secondary
storage [14], providing new insights into the solution of computational problems
in external memory. In the classical read-only streaming model, algorithms are
constrained to access the input data sequentially in one (or few) passes, using
only a small amount of working memory, typically much smaller than the input
size [14, 18, 19]. Usual parameters of the model are the working memory size s
and the number of passes p that are performed over the data, which are usually
Supported in part by the Sixth Framework Programme of the EU under contract
number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”),
and by the Italian MIUR Project “MAINSTREAM: Algorithms for massive infor-
mation structures and data streams”.
L. Kučera and A. Kučera (Eds.): MFCS 2007, LNCS 4708, pp. 194–205, 2007.
c Springer-Verlag Berlin Heidelberg 2007
