Lower Bounds for Multi-Pass Processing of Multiple Data Streams

Author Nicole Schweikardt



PDF
Thumbnail PDF

File

LIPIcs.STACS.2009.1857.pdf
  • Filesize: 106 kB
  • 12 pages

Document Identifiers

Author Details

Nicole Schweikardt

Cite AsGet BibTex

Nicole Schweikardt. Lower Bounds for Multi-Pass Processing of Multiple Data Streams. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 51-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1857

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 \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.
Keywords
  • Data streams
  • Lower bounds
  • Machine models
  • Automata
  • The set disjointness problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail