TY  - CONF
A1  - Schweikardt, Nicole
T1  - Lower bounds for multi-pass processing of multiple data streams
T2  - Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science ; Theoretical Aspects of Computer Science 2009 (Freiburg)
N2  - 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.
KW  - data streams
KW  - lower bounds
KW  - machine models
KW  - automata
KW  - the set disjointness problem
Y1  - 2009
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7198
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71881
SN  - 978-3-939897-09-5
N1  - (c) Nicole Schweikardt ; CC Creative Commons Attribution-NoDerivs License
N1  - 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
SP  - 51
EP  - 62
ER  -