In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically just one. These algorithms are designed to operate with limited memory, generally logarithmic in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

As a result of these constraints, streaming algorithms often produce approximate answers based on a summary or "sketch" of the data stream.

History

Though streaming algorithms had already been studied by Munro and Paterson^[1] as early as 1978, as well as Philippe Flajolet and G. Nigel Martin in 1982/83,^[2] the field of streaming algorithms was first formalized and popularized in a 1996 paper by Noga Alon, Yossi Matias, and Mario Szegedy.^[3] For this paper, the authors later won the Gödel Prize in 2005 "for their foundational contribution to streaming algorithms." There has since been a large body of work centered around data streaming algorithms that spans a diverse spectrum of computer science fields such as theory, databases, networking, and natural language processing.

Semi-streaming algorithms were introduced in 2005 as a relaxation of streaming algorithms for graphs,^[4] in which the space allowed is linear in the number of vertices n, but only logarithmic in the number of edges m. This relaxation is still meaningful for dense graphs, and can solve interesting problems (such as connectivity) that are insoluble in ${\displaystyle o(n)}$ space.

Models

Data stream model

In the data stream model, some or all of the input is represented as a finite sequence of integers (from some finite domain) which is generally not available for random access, but instead arrives one at a time in a "stream".^[5] If the stream has length n and the domain has size m, algorithms are generally constrained to use space that is logarithmic in m and n. They can generally make only some small constant number of passes over the stream, sometimes just one.^[6]

Turnstile and cash register models

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 ${\displaystyle \mathbf {a} =(a_{1},\dots ,a_{n})}$ (initialized to the zero vector ${\displaystyle \mathbf {0} }$) that has updates presented to it in a stream. The goal of these algorithms is to compute functions of ${\displaystyle \mathbf {a} }$ using considerably less space than it would take to represent ${\displaystyle \mathbf {a} }$ precisely. There are two common models for updating such streams, called the "cash register" and "turnstile" models.^[7]

In the cash register model, each update is of the form ${\displaystyle \langle i,c\rangle }$, so that ${\displaystyle a_{i}}$ is incremented by some positive integer ${\displaystyle c}$. A notable special case is when ${\displaystyle c=1}$ (only unit insertions are permitted).

In the turnstile model, each update is of the form ${\displaystyle \langle i,c\rangle }$, so that ${\displaystyle a_{i}}$ is incremented by some (possibly negative) integer ${\displaystyle c}$. In the "strict turnstile" model, no ${\displaystyle a_{i}}$ at any time may be less than zero.

Sliding window model

Several papers also consider the "sliding window" model.^{[citation needed]} 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.^{[citation needed]}

Evaluation

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2021) (Learn how and when to remove this message)

The performance of an algorithm that operates on data streams is measured by three basic factors:

• The number of passes the algorithm must make over the stream.
• The available memory.
• The running time of the algorithm.

These algorithms have many similarities with online algorithms since they both require decisions to be made before all data are available, but they are not identical. Data stream algorithms only have limited memory available but they may be able to defer action until a group of points arrive, while online algorithms are required to take action as soon as each point arrives.

If the algorithm is an approximation algorithm then the accuracy of the answer is another key factor. The accuracy is often stated as an ${\displaystyle (\epsilon ,\delta )}$ approximation meaning that the algorithm achieves an error of less than ${\displaystyle \epsilon }$ with probability ${\displaystyle 1-\delta }$.

Applications

Streaming algorithms have several applications in networking such as monitoring network links for elephant flows, counting the number of distinct flows, estimating the distribution of flow sizes, and so on.^[8] They also have applications in databases, such as estimating the size of a join ^{[citation needed]}.

Some streaming problems

Frequency moments

The kth frequency moment of a set of frequencies ${\displaystyle \mathbf {a} }$ is defined as ${\displaystyle F_{k}(\mathbf {a} )=\sum _{i=1}^{n}a_{i}^{k}}$.

The first moment ${\displaystyle F_{1}}$ is simply the sum of the frequencies (i.e., the total count). The second moment ${\displaystyle F_{2}}$ is useful for computing statistical properties of the data, such as the Gini coefficient of variation. ${\displaystyle F_{\infty }}$ is defined as the frequency of the most frequent items.

The seminal paper of Alon, Matias, and Szegedy dealt with the problem of estimating the frequency moments.^{[citation needed]}

Calculating frequency moments

A direct approach to find the frequency moments requires to maintain a register m_i for all distinct elements a_i ∈ (1,2,3,4,...,N) which requires at least memory of order ${\displaystyle \Omega (N)}$.^[3] But we have space limitations and require an algorithm that computes in much lower memory. This can be achieved by using approximations instead of exact values. An algorithm that computes an (ε,δ)approximation of F_k, where F'_k is the (ε,δ)- approximated value of F_k.^[9] Where ε is the approximation parameter and δ is the confidence parameter.^[10]

Calculating F₀ (distinct elements in a DataStream)

FM-Sketch algorithm

Flajolet et al. in ^[2] introduced probabilistic method of counting which was inspired from a paper by Robert Morris.^[11] Morris in his paper says that if the requirement of accuracy is dropped, a counter n can be replaced by a counter log n which can be stored in log log n bits.^[12] Flajolet et al. in ^[2] improved this method by using a hash function h which is assumed to uniformly distribute the element in the hash space (a binary string of length L).

${\displaystyle h:\rightarrow }$

Let bit(y,k) represent the kth bit in binary representation of y

${\displaystyle y=\sum _{k\geq 0}\mathrm {bit} (y,k)*2^{k}}$

Let ${\displaystyle \rho (y)}$ represents the position of least significant 1-bit in the binary representation of y_i with a suitable convention for ${\displaystyle \rho (0)}$.

${\displaystyle \rho (y)={\begin{cases}\mathrm {Min} (k:\mathrm {bit} (y,k)==1)&{\text{if }}y>0\\L&{\text{if }}y=0\end{cases}}}$

Let A be the sequence of data stream of length M whose cardinality need to be determined. Let BITMAP be the

hash space where the ρ(hashedvalues) are recorded. The below algorithm then determines approximate cardinality of A.

Procedure FM-Sketch:

    for i in 0 to L − 1 do
        BITMAP := 0 
    end for
    for x in A: do
Zdroj:https://en.wikipedia.org?pojem=Streaming_algorithm
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.