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.
Read more about this topic: Streaming Algorithm
Famous quotes containing the word models:
“Grandparents can be role models about areas that may not be significant to young children directly but that can teach them about patience and courage when we are ill, or handicapped by problems of aging. Our attitudes toward retirement, marriage, recreation, even our feelings about death and dying may make much more of an impression than we realize.”
—Eda Le Shan (20th century)
“Friends broaden our horizons. They serve as new models with whom we can identify. They allow us to be ourselves—and accept us that way. They enhance our self-esteem because they think we’re okay, because we matter to them. And because they matter to us—for various reasons, at various levels of intensity—they enrich the quality of our emotional life.”
—Judith Viorst (20th century)
“... your problem is your role models were models.”
—Jane Wagner (b. 1935)