Incomputer science,streaming algorithms are algorithms for processingdata streams in which the input is presented as asequence of items and can be examined in only a few passes, typicallyjust one. These algorithms are designed to operate with limited memory, generallylogarithmic 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.

Though streaming algorithms had already been studied by Munro and Paterson^[1] as early as 1978, as well asPhilippe Flajolet and G. Nigel Martin in 1982/83,^[2] the field of streaming algorithms was first formalized and popularized in a 1996 paper byNoga Alon,Yossi Matias, andMario Szegedy.^[3] For this paper, the authors later won theGö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 verticesn, but only logarithmic in the number of edgesm. This relaxation is still meaningful for dense graphs, and can solve interesting problems (such as connectivity) that are insoluble in${\displaystyle o(n)}$ space.

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 forrandom access, but instead arrives one at a time in a "stream".^[5] If the stream has lengthn and the domain has sizem, algorithms are generally constrained to use space that islogarithmic inm andn. They can generally make only some small constant number of passes over the stream, sometimes justone.^[6]

Much of the streaming literature is concerned with computing statistics onfrequency distributions that are too large to be stored. For this class ofproblems, 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 computefunctions of${\displaystyle \mathbf{a}}$ using considerably less space than itwould take to represent${\displaystyle \mathbf{a}}$ precisely. There are twocommon 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 ⟨i,c⟩}$, so that${\displaystyle a_i}$ is incremented by some positiveinteger${\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 ⟨i,c⟩}$, 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.

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 thestream. As the stream progresses, items from the end of the window areremoved from consideration while new items from the stream take theirplace.

Besides the above frequency-based problems, some other types of problemshave also been studied. Many graph problems are solved in the settingwhere theadjacency matrix or theadjacency list of the graph is streamed insome unknown order. There are also some problems that are very dependenton the order of the stream (i.e., asymmetric functions), such as countingthe number of inversions in a stream and finding the longest increasingsubsequence.^{[citation needed]}

This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(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 withonline 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 (ϵ,\delta )}$ approximation meaning that the algorithm achieves an error of less than${\displaystyle ϵ}$ with probability${\displaystyle 1-\delta }$.

Streaming algorithms have several applications innetworking such asmonitoring network links forelephant flows, counting the number ofdistinct flows, estimating the distribution of flow sizes, and soon.^[8] They also have applications indatabases, such as estimating the size of ajoin^{[citation needed]}.

Thekth 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 theGini coefficientof variation.${\displaystyle F_{\mathrm{\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]}

A direct approach to find the frequency moments requires to maintain a registerm_i for all distinct elementsa_i ∈ (1,2,3,4,...,N) which requires at least memoryof order${\displaystyle \mathrm{\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 ofF_k, whereF'_k is the (ε,δ)-approximated value ofF_k.^[9] Whereε is the approximation parameter andδ is the confidence parameter.^[10]

Flajolet et al. in^[2] introduced probabilistic method of counting which was inspired from a paper byRobert Morris.^[11] Morris in his paper says that if the requirement of accuracy is dropped, a countern can be replaced by a counterlogn which can be stored inlog logn bits.^[12] Flajolet et al. in^[2] improved this method by using a hash functionh which is assumed to uniformly distribute the element in the hash space (a binary string of lengthL).

${\displaystyle h:[m]\to [0,2^L-1]}$

Letbit(y,k) represent the kth bit in binary representation ofy

${\displaystyle y=\sum _{k\ge 0}\mathrm{b}\mathrm{i}\mathrm{t}(y,k)\ast 2^k}$

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

LetA be the sequence of data stream of lengthM whose cardinality need to be determined. LetBITMAP [0...L − 1] be the

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

Procedure FM-Sketch:    for i in 0 to L − 1 do        BITMAP[i] := 0     end for    for x in A: do        Index := ρ(hash(x))        if BITMAP[index] = 0 then            BITMAP[index] := 1        end if    end for    B := Position of left most 0 bit of BITMAP[]     return 2 ^ B

If there areN distinct elements in a data stream.

• For${\displaystyle i\gg \log (N)}$ thenBITMAP[i] is certainly 0
• For${\displaystyle i\ll \log (N)}$ thenBITMAP[i] is certainly 1
• For${\displaystyle i\approx \log (N)}$ thenBITMAP[i] is a fringes of 0's and 1's

The previous algorithm describes the first attempt to approximateF₀ in the data stream by Flajolet and Martin. Their algorithm picks a randomhash function which they assume to uniformly distribute the hash values in hash space.

Bar-Yossef et al. in^[10] introduced k-minimum value algorithm for determining number of distinct elements in data stream. They used a similar hash functionh which can be normalized to [0,1] as${\displaystyle h:[m]\to [0,1]}$. But they fixed a limitt to number of values in hash space. The value oft is assumed of the order${\displaystyle O\left({\displaystyle \frac{1}{{\epsilon }_2}}\right)}$ (i.e. less approximation-valueε requires moret). KMV algorithm keeps onlyt-smallest hash values in the hash space. After all them values of stream have arrived,${\displaystyle \upsilon =\mathrm{M}\mathrm{a}\mathrm{x}(h(a_i))}$ is used to calculate${\displaystyle F_0^{\prime }={\displaystyle \frac{t}{\upsilon }}}$. That is, in a close-to uniform hash space, they expect at-leastt elements to be less than${\displaystyle O\left({\displaystyle \frac{t}{F_0}}\right)}$.

Procedure 2 K-Minimum ValueInitialize first t values of KMV for a in a1 to an do    if h(a) < Max(KMV) then        Remove Max(KMV) from KMV set        Insert h(a) to KMV     end ifend for return t/Max(KMV)

KMV algorithm can be implemented in${\displaystyle O\left(\left({\displaystyle \frac{1}{{\epsilon }_2}}\right)\cdot \log (m)\right)}$ memory bits space. Each hash value requires space of order${\displaystyle O(\log (m))}$ memory bits. There are hash values of the order${\displaystyle O\left({\displaystyle \frac{1}{{\epsilon }_2}}\right)}$. The access time can be reduced if we store thet hash values in a binary tree. Thus the time complexity will be reduced to${\displaystyle O\left(\log \left({\displaystyle \frac{1}{\epsilon }}\right)\cdot \log (m)\right)}$.

Alon et al. estimatesF_k by defining random variables that can be computed within given space and time.^[3] The expected value of random variables gives the approximate value ofF_k.

Assume length of sequencem is known in advance. Then construct a random variableX as follows:

• Selecta_p be a random member of sequenceA with index atp,${\displaystyle a_p=l\in (1,2,3,\dots ,n)}$
• Let${\displaystyle r=|\{q:q\ge p,a_q=l\}|}$, represents the number of occurrences ofl within the members of the sequenceA followinga_p.
• Random variable${\displaystyle X=m(r^k-(r-1{)}^k)}$.

AssumeS₁ be of the order${\displaystyle O(n^{1-1/k}/{\lambda }^2)}$ andS₂ be of the order${\displaystyle O(\log (1/\epsilon ))}$. Algorithm takesS₂ random variable${\displaystyle Y_1,Y_2,...,Y_{S2}}$ and outputs the median${\displaystyle Y}$ . WhereY_i is the average ofX_ij where 1 ≤j ≤S₁.

Now calculate expectation of random variableE(X).

From the algorithm to calculateF_k discussed above, we can see that each random variableX stores value ofa_p andr. So, to computeX we need to maintain onlylog(n) bits for storinga_p andlog(n) bits for storingr. Total number of random variableX will be the⁠${\displaystyle S_1\ast S_2}$⁠.

Hence the total space complexity the algorithm takes is of the order of${\displaystyle O\left({\displaystyle \frac{k\log \frac{1}{\epsilon }}{{\lambda }^2}}{n}^{1-\frac{1}{k}}\left(\log n+\log m\right)\right)}$

The previous algorithm calculates${\displaystyle F_2}$ in order of${\displaystyle O(\sqrt{n}(\log m+\log n))}$ memory bits. Alon et al. in^[3] simplified this algorithm using four-wise independent random variable with values mapped to${\displaystyle \{-1,1\}}$.

This further reduces the complexity to calculate${\displaystyle F_2}$ to${\displaystyle O\left({\displaystyle \frac{\log \frac{1}{\epsilon }}{{\lambda }^2}}\left(\log n+\log m\right)\right)}$

In the data stream model, thefrequent elements problem is to output a set of elements that constitute more than some fixed fraction of the stream. A special case is themajority problem, which is to determine whether or not any value constitutes a majority of the stream.

More formally, fix some positive constantc > 1, let the length of the stream bem, and letf_i denote the frequency of valuei in the stream. The frequent elements problem is to output theset {i |f_i > m/c }.^[13]

Some notable algorithms are:

• Boyer–Moore majority vote algorithm
• Count-Min sketch
• Lossy counting
• Multi-stageBloom filters
• Misra–Gries heavy hitters algorithm
• Misra–Gries summary

Detecting events in data streams is often done using a heavy hitters algorithm as listed above: the most frequent items and their frequency are determined using one of these algorithms, then the largest increase over the previous time point is reported as trend. This approach can be refined by using exponentially weightedmoving averages and variance for normalization.^[14]

Counting the number of distinct elements in a stream (sometimes called theF₀ moment) is another problem that has been well studied.The first algorithm for it was proposed by Flajolet and Martin. In 2010,Daniel Kane,Jelani Nelson and David Woodruff found an asymptotically optimal algorithm for this problem.^[15] It usesO(ε² + logd) space, withO(1) worst-case update and reporting times, as well as universal hash functions and ar-wise independent hash family wherer = Ω(log(1/ε) / log log(1/ε)).

The (empirical) entropy of a set of frequencies${\displaystyle \mathbf{a}}$ isdefined as${\displaystyle F_k(\mathbf{a})=\sum _{i=1}^n\frac{a_i}{m}\log \frac{a_i}{m}}$, where${\displaystyle m=\sum _{i=1}^n{a}_i}$.

Learn a model (e.g. aclassifier) by a single pass over a training set.

• Feature hashing
• Stochastic gradient descent

Lower bounds have been computed for many of the data streaming problemsthat have been studied. By far, the most common technique for computingthese lower bounds has been usingcommunication complexity.^{[citation needed]}

• Data stream mining
• Data stream clustering
• Online algorithm
• Stream processing
• Sequential algorithm

• Alon, Noga;Matias, Yossi;Szegedy, Mario (1999), "The space complexity of approximating the frequency moments",Journal of Computer and System Sciences,58 (1):137–147,doi:10.1006/jcss.1997.1545,ISSN 0022-0000. First published asAlon, Noga; Matias, Yossi; Szegedy, Mario (1996), "The space complexity of approximating the frequency moments",Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996), pp. 20–29,CiteSeerX 10.1.1.131.4984,doi:10.1145/237814.237823,ISBN 978-0-89791-785-8,S2CID 1627911.
• Babcock, Brian; Babu, Shivnath; Datar, Mayur;Motwani, Rajeev;Widom, Jennifer (2002), "Models and issues in data stream systems",Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002)(PDF), pp. 1–16,CiteSeerX 10.1.1.138.190,doi:10.1145/543613.543615,ISBN 978-1-58113-507-7,S2CID 2071130, archived fromthe original(PDF) on 2017-07-09, retrieved2013-07-15.
• Flajolet, Philippe; Martin, G. Nigel (1985)."Probabilistic counting algorithms for data base applications"(PDF).Journal of Computer and System Sciences.31 (2):182–209.doi:10.1016/0022-0000(85)90041-8. Retrieved2016-12-11.
• Gilbert, A. C.; Kotidis, Y.;Muthukrishnan, S.; Strauss, M. J. (2001),"Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries"(PDF),Proceedings of the International Conference on Very Large Data Bases:79–88.
• Kane, Daniel M.; Nelson, Jelani; Woodruff, David P. (2010). "An optimal algorithm for the distinct elements problem".Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. PODS '10. New York, NY, USA: ACM. pp. 41–52.CiteSeerX 10.1.1.164.142.doi:10.1145/1807085.1807094.ISBN 978-1-4503-0033-9.S2CID 10006932..
• Karp, R. M.;Papadimitriou, C. H.;Shenker, S. (2003), "A simple algorithm for finding frequent elements in streams and bags",ACM Transactions on Database Systems,28 (1):51–55,CiteSeerX 10.1.1.116.8530,doi:10.1145/762471.762473,S2CID 952840.
• Lall, Ashwin; Sekar, Vyas; Ogihara, Mitsunori; Xu, Jun; Zhang, Hui (2006). "Data streaming algorithms for estimating entropy of network traffic".Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006). p. 145.doi:10.1145/1140277.1140295.hdl:1802/2537.ISBN 978-1-59593-319-5.S2CID 240982..
• Xu, Jun (Jim) (2007),A Tutorial on Network Data Streaming(PDF).
• Heath, D., Kasif, S., Kosaraju, R., Salzberg, S., Sullivan, G., "Learning Nested Concepts With Limited Storage", Proceeding IJCAI'91 Proceedings of the 12th international joint conference on Artificial intelligence - Volume 2, Pages 777–782, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA ©1991
• Morris, Robert (1978), "Counting large numbers of events in small registers",Communications of the ACM,21 (10):840–842,doi:10.1145/359619.359627,S2CID 36226357.

• Streaming algorithms

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from November 2017
• Articles with unsourced statements from April 2021
• Articles needing additional references from April 2021
• All articles needing additional references
• Articles with unsourced statements from March 2013