Extending the Streaming Model: Sorting and Streaming Networks

Matthias Ruhl, Gagan Aggarwal, Mayur Datar and Sridhar Rajagopalan

DIMACS Working Group Meeting on Streaming Data Analysis
Piscataway, NJ, March 2003

[Postscript, 21KB]

[Compressed Postscript, 9KB]

[PDF, 12KB]

Talk Abstract

The need to deal with massive data sets in many practical applications has led to a growing interest in computational models appropriate for large inputs. One such model is "streaming computations", where inputs are provided as a long sequence of data items. In this model, functions are computed by a machine with small local memory making one or a small number of linear passes on the input stream. In this talk, motivated by practical considerations, we discuss two extensions of this computational model. Despite being quite different in motivation and form, these extensions turn out to be closely related in their computational power. This suggests that the computational class defined by them is somewhat stable and deserves further study.

Back to publications