Streaming Algorithm - Models

Models

In the data stream model, some or all of the input data that are to be operated on are not available for random access from disk or memory, but rather arrive as one or more continuous data streams.

Streams can be denoted as an ordered sequence of points (or "updates") that must be accessed in order and can be read only once or a small number of times.

Much of the streaming literature is concerned with computing statistics on frequency distributions that are too large to be stored. For this class of problems, there is a vector (initialized to the zero vector ) that has updates presented to it in a stream. The goal of these algorithms is to compute functions of using considerably less space than it would take to represent precisely. There are two common models for updating such streams, called the "cash register" and "turnstile" models.

In the cash register model each update is of the form , so that is incremented by some positive integer . A notable special case is when (only unit insertions are permitted).

In the turnstile model each update is of the form , so that is incremented by some (possible negative) integer . In the "strict turnstile" model, no at any time may be less than zero.

Several papers also consider the "sliding window" model. In this model, the function of interest is computing over a fixed-size window in the stream. As the stream progresses, items from the end of the window are removed from consideration while new items from the stream take their place.

Besides the above frequency-based problems, some other types of problems have also been studied. Many graph problems are solved in the setting where the adjacency matrix or the adjacency list of the graph is streamed in some unknown order. There are also some problems that are very dependent on the order of the stream (i.e., asymmetric functions), such as counting the number of inversions in a stream and finding the longest increasing subsequence.