Extending the Streaming Model: Sorting and Streaming Networks
Matthias Rühl, Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan · 2003
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 ” [MP80, AMS99, HRR99], 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. Streaming and Sorting. The first extension is motivated by two facts about modern computing platforms. First, storage on disk is readily available and cheap (in the order of a few dollars per gigabyte). This implies that large amounts of temporary storage can, and should, be used, suggesting that the classical streaming model may be too restrictive in not allowing data storage at intermediate stages of the computation. Second, sorting a large collection of fixed size records can be done extremely efficiently on commodity hardware, with rates that bottleneck the I/O subsystem (see for instance [Aga96, ADADC 97, Wyl99, Cha]). This contrasts with the fact that sorting is formally hard in streaming models. This seems to suggest that the