Lower Bounds for Multi-Pass Processing of Multiple Data Streams

Abstract : This paper gives a brief overview of computation models for data stream processing, and it introduces a new model for multi-pass processing of multiple streams, the so-called mp2s-automata. Two algorithms for solving the set disjointness problem wi th these automata are presented. The main technical contribution of this paper is the proof of a lower bound on the size of memory and the number of heads that are required for solvin g the set disjointness problem with mp2s-automata.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.51-62, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359686
Contributeur : Publications Loria <>
Soumis le : lundi 9 février 2009 - 10:59:30
Dernière modification le : mercredi 11 février 2009 - 16:18:33
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:30:47

Fichiers

Schweikardt-STACS09_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359686, version 1
  • ARXIV : 0902.1605

Collections

Citation

Nicole Schweikardt. Lower Bounds for Multi-Pass Processing of Multiple Data Streams. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.51-62, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359686〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

180