Streaming algorithm

In computer science, streaming algorithms process input data streams as a sequence of items, typically making just one pass (or a few passes) through the data. 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.

In computer science, streaming algorithms process input data streams as a sequence of items, typically making just one pass (or a few passes) through the data. 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 as early as 1978, as well as Philippe Flajolet and G. Nigel Martin in 1982/83, the field of streaming algorithms was first formalized and popularized in a 1996 paper by Noga Alon, Yossi Matias, and Mario Szegedy. 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, in which the space allowed is linear in the number of vertices , but only logarithmic in the number of edges . This relaxation is still meaningful for dense graphs, and can solve interesting problems (such as connectivity) that are insoluble in o(n) space. ==Models== problems, there is a vector \mathbf{a} = (a_1, \dots, a_n) (initialized to the zero vector \mathbf{0} ) that has updates presented to it in a stream. The goal of these algorithms is to compute functions of \mathbf{a} using considerably less space than it would take to represent \mathbf{a} 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 \langle i, c\rangle , so that a_i is incremented by some positive integer c . A notable special case is when c = 1 (only unit insertions are permitted). In the turnstile model, each update is of the form \langle i, c\rangle , so that a_i is incremented by some (possibly negative) integer c . In the "strict turnstile" model, no a_i at any time may be less than zero. ==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. They also have applications in databases, such as estimating the size of a join . ==Some streaming problems== ===Frequency moments=== The th frequency moment of a set of frequencies \mathbf{a} is defined as F_k(\mathbf{a}) = \sum_{i=1}^n a_i^k . The first moment F_1 is simply the sum of the frequencies (i.e., the total count). The second moment F_2 is useful for computing statistical properties of the data, such as the Gini coefficient of variation. 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. y = \sum_{k\geq0} \mathrm{bit}(y,k)*2^{k} Let \rho(y) represents the position of least significant 1-bit in the binary representation of with a suitable convention for \rho(0) . \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 [0...L − 1] 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[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 are N distinct elements in a data stream. For i \gg \log(N) then BITMAP[i] is certainly 0 For i \ll \log(N) then BITMAP[i] is certainly 1 For i \approx \log(N) then BITMAP[i] is a fringes of 0's and 1's Bar-Yossef et al. in introduced k-minimum value algorithm for determining number of distinct elements in data stream. They used a similar hash function h which can be normalized to [0,1] as h:[m] \rightarrow [0,1] . But they fixed a limit t to number of values in hash space. The value of t is assumed of the order O\left(\dfrac{1}{\varepsilon_{2}}\right) (i.e. less approximation-value ε requires more t). KMV algorithm keeps only t-smallest hash values in the hash space. After all the m values of stream have arrived, \upsilon= \mathrm{Max}(h(a_{i} )) is used to calculate F'_{0}=\dfrac{t}{\upsilon} . That is, in a close-to uniform hash space, they expect at-least t elements to be less than O\left(\dfrac{t}{F_{0}}\right) . Procedure 2 K-Minimum Value Initialize first t values of KMV for a in a1 to an do if h(a) Select be a random member of sequence with index at , a_p=l \in(1,2,3,\ldots,n) Let r=|\{q:q\geq p,a_q=l\}| , represents the number of occurrences of within the members of the sequence following . Random variable X=m(r^k-(r-1)^k) . Assume S 1 be of the order O(n^{1-1/k}/\lambda^{2}) and S 2 be of the order O(\log(1/\varepsilon)) . Algorithm takes S 2 random variable Y_1,Y_2,...,Y_{S2} and outputs the median Y . Where is the average of where 1 ≤ j ≤ S 1 . Now calculate expectation of random variable . \begin{array}{lll} E(X) &=& \sum_{i=1}^{n} \sum_{i=1}^{m_i} (j^k-(j-1)^k) \\ &=& \frac{m}{m} [(1^k+(2^k-1^k)+\ldots+ (m_{1}^{k} - (m_{1}-1)^{k})) \\ &&\;+\; (1^k+(2^k-1^k)+\ldots+ (m_{2}^{k} - (m_{2}-1)^{k}))+\ldots \\ &&\;+\; (1^k+(2^k-1^k)+\ldots+ (m_{n}^{k} - (m_{n}-1)^{k}))] \\ &=& \sum_{i=1}^{n} m_{i}^{k} = F_{k} \end{array} ===Frequent elements=== In the data stream model, the frequent elements problem is to output a set of elements that constitute more than some fixed fraction of the stream. A special case is the majority problem, which is to determine whether or not any value constitutes a majority of the stream. More formally, fix some positive constant > 1, let the length of the stream be , and let denote the frequency of value in the stream. The frequent elements problem is to output the set { | > m/c }. Some notable algorithms are: Boyer–Moore majority vote algorithm Count-Min sketch Lossy counting Multi-stage Bloom filters Misra–Gries heavy hitters algorithm Misra–Gries summary ===Event detection=== 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 weighted moving averages and variance for normalization. ===Counting distinct elements=== Counting the number of distinct elements in a stream (sometimes called the 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. It uses space, with worst-case update and reporting times, as well as universal hash functions and a -wise independent hash family where . ===Entropy=== The (empirical) entropy of a set of frequencies \mathbf{a} is defined as F_k(\mathbf{a}) = \sum_{i=1}^n \frac{a_i}{m}\log{\frac{a_i}{m}} , where m = \sum_{i=1}^n a_i . ===Online learning=== Learn a model (e.g. a classifier) by a single pass over a training set. Feature hashing Stochastic gradient descent ==Lower bounds== Lower bounds have been computed for many of the data streaming problems that have been studied. By far, the most common technique for computing these lower bounds has been using communication complexity. ==Notes== ==References== . First published as . . . . . . . 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 .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375097691 under CC BY-SA 4.0; modifications have been made.