Lower bounds for multi-pass processing of multiple data streams

  • 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 with 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 solving the set disjointness problem with mp2s-automata.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Nicole Schweikardt
URN:urn:nbn:de:hebis:30-71881
ISBN:978-3-939897-09-5
Parent Title (English):Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science ; Theoretical Aspects of Computer Science 2009 (Freiburg)
Document Type:Conference Proceeding
Language:English
Date of Publication (online):2009/10/21
Year of first Publication:2009
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Creating Corporation:26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Freiburg : Germany (2009)
Release Date:2009/10/21
Tag:automata; data streams; lower bounds; machine models; the set disjointness problem
Page Number:12
First Page:51
Last Page:62
Note:
(c) Nicole Schweikardt ; CC Creative Commons Attribution-NoDerivs License
Note:
ACM Classification: 		
F.: Theory of Computation/F.1: COMPUTATION BY ABSTRACT DEVICES/F.1.1: Models of Computation
F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems
F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.3: Tradeoffs between Complexity Measures
Source:Author manuscript, published in "26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 Freiburg (2009) 51-62"
HeBIS-PPN:219881502
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoCreative Commons - Namensnennung-Keine Bearbeitung

OPUS4 Logo