Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Publications Loria Connect 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


Files produced by the author(s)


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



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⟩



Record views


Files downloads