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.
https://hal.inria.fr/inria-00359686 Contributor : Publications LoriaConnect in order to contact the contributor Submitted on : Monday, February 9, 2009 - 10:59:30 AM Last modification on : Wednesday, February 11, 2009 - 4:18:33 PM Long-term archiving on: : Tuesday, June 8, 2010 - 8:30:47 PM
Nicole Schweikardt. Lower Bounds for Multi-Pass Processing of Multiple Data Streams. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.51-62. ⟨inria-00359686⟩