10.4230/LIPICS.STACS.2009.1857
Schweikardt, Nicole
Nicole
Schweikardt
Lower Bounds for Multi-Pass Processing of Multiple Data Streams
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2009
Data streams
Lower bounds
Machine models
Automata
The set disjointness problem
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
2009
2009-02-19
2009-02-19
2009-02-19
en
urn:nbn:de:0030-drops-18575
10.4230/LIPIcs.STACS.2009
978-3-939897-09-5
1868-8969
10.4230/LIPIcs.STACS.2009
LIPIcs, Volume 3, STACS 2009
26th International Symposium on Theoretical Aspects of Computer Science
2013
3
3
51
62
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Marion, Jean-Yves
Jean-Yves
Marion
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2009
3
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
109419 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 \emph{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.
LIPIcs, Vol. 3, 26th International Symposium on Theoretical Aspects of Computer Science, pages 51-62