• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Parallel Algorithms are Good for Streaming

Thumbnail
View/Open
cahierLamsade234.pdf (263.4Kb)
Date
2006
Publisher city
Paris
Publisher
Université Paris-Dauphine
Collection title
Cahier du LAMSADE
Collection Id
234
Dewey
Recherche opérationnelle
Sujet
W-stream model; combinatorial problems; streaming; PRAM algorithms
URI
https://basepub.dauphine.fr/handle/123456789/6303
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Demetrescu, Camil
Escoffier, Bruno
Moruz, Gabriel
Ribichini, Andrea
Type
Document de travail / Working paper
Item number of pages
16
Abstract (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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.