Lower Bounds for Multi-Pass Processing of Multiple Data Streams

Details Lower Bounds for Multi-Pass Processing of Multiple Data Streams Lower Bounds for Multi-Pass Processing of Multiple Data Streams

2009-02-10

arxiv.org/abs/0902.1605v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 51-62

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Lower Bounds for Multi-Pass Processing of Multiple Data Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lower Bounds for Multi-Pass Processing of Multiple Data Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Bounds for Multi-Pass Processing of Multiple Data Streams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-19765