View source for Streaming algorithm

In [[computer science]], '''streaming algorithms''' are algorithms for processing [[data stream]]s in which the input is presented as a [[sequence]] of items and can be examined in only a few passes (typically just one). In most models, these algorithms have access to limited memory (generally [[L (complexity)|logarithmic]] in the size of and/or the maximum value in the stream). They may also have limited processing time per item.

These constraints may mean that an algorithm produces an approximate answer based on a summary or "sketch" of the data stream.

==History==

Though streaming algorithms had already been studied by Munro and Paterson<ref>{{Harvtxt|Munro|Paterson|1980}}</ref> as early as 1980, as well as [[Philippe Flajolet]] and G. Nigel Martin in 1982/83,<ref name=":0"/> the field of streaming algorithms was first formalized and popularized in a 1996 paper by [[Noga Alon]], [[Yossi Matias]], and [[Mario Szegedy]].<ref name=":1">{{Harvtxt|Alon|Matias|Szegedy|1996}}</ref> 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 algorithm]]s were introduced in 2005 as a relaxation of streaming algorithms for graphs [https://dl.acm.org/citation.cfm?id=1132638], in which the space allowed is linear in the number of vertices {{var|n}}, but only logarithmic in the number of edges {{var|m}}.  This relaxation is still meaningful for dense graphs, and can solve interesting problems (such as connectivity) that are insoluble in <math>o(n)</math> 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".<ref>{{Cite book|last=Babcock|first=Brian|last2=Babu|first2=Shivnath|last3=Datar|first3=Mayur|last4=Motwani|first4=Rajeev|last5=Widom|first5=Jennifer|date=2002|title=Models and Issues in Data Stream Systems|journal=Proceedings of the Twenty-first ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems|series=PODS '02|location=New York, NY, USA|publisher=ACM|pages=1–16|doi=10.1145/543613.543615|isbn=978-1581135077|citeseerx=10.1.1.138.190}}</ref> If the stream has length {{var|n}} and the domain has size {{var|m}}, algorithms are generally constrained to use space that is [[L (complexity)|logarithmic]] in {{var|m}} and {{var|n}}. They can generally make only some small constant number of passes over the stream, sometimes just one.<ref>{{Cite book|last=Bar-Yossef|first=Ziv|last2=Jayram|first2=T. S.|last3=Kumar|first3=Ravi|last4=Sivakumar|first4=D.|last5=[[Luca Trevisan|Trevisan]]|first5=Luca|date=2002-09-13|title=Counting Distinct Elements in a Data Stream|journal=Randomization and Approximation Techniques in Computer Science|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=1–10|doi=10.1007/3-540-45726-7_1|isbn=978-3540457268|citeseerx=10.1.1.12.6276}}</ref>

=== 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 <math>\mathbf{a} = (a_1, \dots, a_n)</math>
(initialized to the zero vector <math>\mathbf{0}</math>) that has updates
presented to it in a stream. The goal of these algorithms is to compute
functions of <math>\mathbf{a}</math> using considerably less space than it
would take to represent <math>\mathbf{a}</math> precisely. There are two
common models for updating such streams, called the "cash register" and
"turnstile" models.<ref
name="turnstile">{{harvtxt|Gilbert|Kotidis|Muthukrishnan|Strauss|2001}}</ref>

In the cash register model each update is of the form <math>\langle i,
c\rangle</math>, so that <math>a_i</math> is incremented by some positive
integer <math>c</math>. A notable special case is when <math>c = 1</math>
(only unit insertions are permitted).

In the turnstile model each update is of the form <math>\langle i,
c\rangle</math>, so that <math>a_i</math> is incremented by some (possibly negative) integer <math>c</math>. In the "strict turnstile" model, no
<math>a_i</math> at any time may be less than zero.

=== Sliding window model ===

Several papers also consider the "sliding window" model.{{Citation needed|date=November 2017}} 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.

== Evaluation ==

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 <math>(\epsilon,\delta)</math> approximation meaning that the algorithm achieves an error of less than <math>\epsilon</math> with probability <math>1-\delta</math>.

==Applications==

Streaming algorithms have several applications in [[Computer network|networking]] such as
monitoring network links for [[elephant flow]]s, counting the number of
distinct flows, estimating the distribution of flow sizes, and so
on.<ref>{{Harvtxt|Xu|2007}}</ref> They also have applications in
databases, such as estimating the size of a [[Join (SQL)|join]] {{Citation needed|date=March 2013}}.
<!--

===Flowsize distribution and subpopulation flowsize distribution===
===Traffic and flow matrix estimation===
===Super-spreaders===

-->

==Some streaming problems==

===Frequency moments===

The {{mvar|k}}th frequency moment of a set of frequencies
<math>\mathbf{a}</math> is defined as <math>F_k(\mathbf{a}) = \sum_{i=1}^n
a_i^k</math>.

The first moment <math>F_1</math> is simply the sum of the frequencies
(i.e., the total count). The second moment <math>F_2</math> is useful for
computing statistical properties of the data, such as the [[Gini coefficient]]
of variation. <math>F_{\infty}</math> is defined as the frequency of the
most frequent item(s).

The seminal paper of Alon, Matias, and Szegedy dealt with the
problem of estimating the frequency moments.

==== Calculating Frequency Moments ====
A direct approach to find the frequency moments requires to maintain a register {{mvar|m<sub>i</sub>}} for all distinct elements {{math|''a''<sub>''i''</sub> ∈ (1,2,3,4,...,''N'')}} which requires at least memory
of order <math>\Omega(N)</math>.<ref name=":1"/> 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 {{mvar|F<sub>k</sub>}}, where {{mvar|F'<sub>k</sub>}} is the (''ε,δ'')-
approximated value of {{mvar|F<sub>k</sub>}}.<ref>{{Cite book|title = Optimal Approximations of the Frequency Moments of Data Streams|publisher = ACM|journal = Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing|date = 2005-01-01|location = New York, NY, USA|isbn = 978-1-58113-960-0|pages = 202–208|series = STOC '05|doi = 10.1145/1060590.1060621|first = Piotr|last = Indyk|first2 = David|last2 = Woodruff}}</ref> Where ''ε'' is the approximation parameter and ''δ'' is the confidence parameter.<ref name=":2">{{Cite book|title = Counting Distinct Elements in a Data Stream|publisher = Springer Berlin Heidelberg|date = 2002-09-13|isbn = 978-3-540-44147-2|pages = 1–10|series = Lecture Notes in Computer Science|first = Ziv|last = Bar-Yossef|first2 = T. S.|last2 = Jayram|first3 = Ravi|last3 = Kumar|first4 = D.|last4 = Sivakumar|first5 = Luca|last5 = Trevisan|editor-first = José D. P.|editor-last = Rolim|editor-first2 = Salil|editor-last2 = Vadhan|doi = 10.1007/3-540-45726-7_1|citeseerx = 10.1.1.12.6276}}</ref>

===== Calculating  ''F''<sub>0</sub> (Distinct Elements in a DataStream) =====
{{Main|Count-distinct problem}}

====== FM-Sketch Algorithm ======
Flajolet et al. in <ref name=":0">{{Harvtxt|Flajolet|Martin|1985}}</ref> introduced probabilistic method of counting which was inspired from a paper by [[Robert_Morris_(cryptographer)|Robert Morris]]<ref>{{Harvtxt|Morris|1978}}</ref>. Morris in his paper says that if the requirement of accuracy is dropped, a counter ''n'' can be replaced by a counter {{math|log ''n''}} which can be stored in {{math|log log ''n''}} bits.<ref>{{Cite journal|title = Approximate counting: A detailed analysis|journal = BIT Numerical Mathematics|date = 1985-03-01|issn = 0006-3835|pages = 113–134|volume = 25|issue = 1|doi = 10.1007/BF01934993|first = Philippe|last = Flajolet|citeseerx = 10.1.1.64.5320}}</ref> Flajolet et al. in <ref name=":0" /> improved this method by using a hash function {{mvar|h}} which is assumed to uniformly distribute the element in the hash space (a binary string of length {{mvar|L}}).

:<math>h:[m] \rightarrow [0,2^{L}-1]</math>

Let {{math|bit(''y,k'')}} represent the kth bit in binary representation of {{mvar|y}}

:<math>y = \sum_{k\geq0} \mathrm{bit}(y,k)*2^{k}</math>

Let <math>\rho(y)</math> represents the position of least
significant 1-bit in the binary representation of {{mvar|y<sub>i</sub>}} with a suitable convention for <math>\rho(0)</math>.

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

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 {{mvar|ρ}}(''hashedvalues'') are recorded. The below algorithm then determines approximate cardinality of ''A''.<pre>
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
</pre>If there are ''N'' distinct elements in a data stream.
* For <math>i \gg \log(N)</math> then ''BITMAP''[''i''] is certainly 0
* For <math>i \ll \log(N)</math> then ''BITMAP''[''i''] is certainly 1
* For <math>i \approx \log(N)</math> then ''BITMAP''[''i''] is a fringes of 0's and 1's

====== K-Minimum Value Algorithm ======
The previous algorithm describes the first attempt to approximate ''F''<sub>0</sub> in the data stream by Flajolet and Martin. Their algorithm picks a random hash function which they assume to uniformly distribute the hash values in hash space.

Bar-Yossef et al. in <ref name=":2" /> 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 <math>h:[m] \rightarrow [0,1]</math>. But they fixed a limit ''t'' to number of values in hash space. The value of ''t'' is assumed of the order <math>O\left(\dfrac{1}{\varepsilon_{2}}\right)</math> (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, <math>\upsilon= \mathrm{Max}(h(a_{i} ))</math> is used to calculate<math>F'_{0}=\dfrac{t}{\upsilon}</math>. That is, in a close-to uniform hash space, they expect at-least ''t'' elements to be less than  <math>O\left(\dfrac{t}{F_{0}}\right)</math>.<pre>
Procedure 2 K-Minimum Value

Initialize 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 if
end for 
return t/Max(KMV)
</pre>

====== Complexity analysis of KMV ======
KMV algorithm can be implemented in <math>O\left(\left(\dfrac{1}{\varepsilon_{2}}\right)\cdot\log(m)\right)</math> memory bits space. Each hash value requires space of order <math>O(\log(m))</math> memory bits. There are hash values of the order <math>O\left(\dfrac{1}{\varepsilon_{2}}\right)</math>. The access time can be reduced if we store the ''t'' hash values in a binary tree. Thus the time complexity will be reduced to <math>O\left(\log\left(\dfrac{1}{\varepsilon}\right)\cdot\log(m)\right)</math>.

===== Calculating {{math|''F''<sub>k</sub>}} =====
Alon et al. in <ref name=":1" /> estimates {{mvar|F<sub>k</sub>}} by defining random variables that can be computed within given space and time. The expected value of random variable gives the approximate value of {{mvar|F<sub>k</sub>}}.

Let us assume length of sequence ''m'' is known in advance.

Construct a random variable ''X'' as follows:
* Select {{mvar|a<sub>p</sub>}} be a random member of sequence {{mvar|A}} with index at {{mvar|p}}, <math>a_p=l \in(1,2,3,\ldots,n)</math>
* Let <math>r=|\{q:q\geq p,a_q=l\}|</math>, represents the number of occurrences of {{mvar|l}} within the members of the sequence {{mvar|A}} following {{mvar|a<sub>p</sub>}}.
* Random variable <math>X=m(r^k-(r-1)^k)</math>.

Assume ''S''<sub>1</sub> be of the order <math>O(n^{1-1/k}/\lambda^{2})</math> and ''S''<sub>2</sub> be of the order <math>O(\log(1/\varepsilon))</math>. Algorithm takes ''S''<sub>2</sub> random
variable ''Y''<sub>1</sub>'',Y''<sub>2</sub>'',...,Y<sub>S</sub>''<sub>2</sub> and outputs the median ''Y'' . Where {{mvar|Y<sub>i</sub>}}  is the average of {{mvar|X<sub>ij</sub>}}
where 1 ≤ ''j'' ≤ ''S''<sub>1</sub>.

Now  calculate expectation of random variable {{math|''E''(''X'')}}.

: <math>\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}</math>

====== Complexity of {{math|''F''<sub>k</sub>}} ======
From the algorithm to calculate {{mvar|F<sub>k</sub>}} discussed above, we can see that each random variable {{mvar|X}} stores value of {{mvar|a<sub>p</sub>}} and {{mvar|r}}. So, to compute {{mvar|X}} we need to maintain only {{math|log(''n'')}} bits for storing {{mvar|a<sub>p</sub>}} and {{math|log(''n'')}} bits for storing {{mvar|r}}. Total number of random variable {{mvar|X}} will be the {{tmath|S_1 * S_2}}.

Hence the total space complexity the algorithm takes is of the order of <math>O\left(\dfrac{k\log{1 \over \varepsilon}}{\lambda^{2}}n^{1-{1 \over k}}\left(\log n + \log m\right)\right)</math>

====== Simpler approach to calculate {{math|''F''<sub>2</sub>}} ======
The previous algorithm calculates <math>F_2</math> in order of <math>O( \sqrt{n}(\log m + \log n))</math> memory bits. Alon et al. in <ref name=":1" /> simplified this algorithm using four-wise independent random variable with values mapped to <math>\{-1,1\}</math>.

This further reduces the complexity to calculate <math>F_2</math>  to <math>O\left(\dfrac{\log{1\over\varepsilon}}{\lambda^{2}}\left(\log n + \log m\right)\right)</math>

===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 {{var|c}} > 1, let the length of the stream be {{var|m}}, and let {{var|f}}<sub>{{var|i}}</sub> denote the frequency of value {{var|i}} in the stream. The frequent elements problem is to output the [[Set (mathematics)|set]] { {{var|i}} | {{var|f}}<sub>{{var|i}}</sub> > m/c }.<ref>{{Cite book|title=Encyclopedia of Algorithms|last=Cormode|first=Graham|date=2014|publisher=Springer US|isbn=9783642278488|editor-last=Kao|editor-first=Ming-Yang|pages=1–5|language=en|doi=10.1007/978-3-642-27848-8_572-1|chapter = Misra-Gries Summaries}}</ref>

Some notable algorithms are:

* [[Boyer–Moore majority vote algorithm]]
* Karp-Papadimitriou-Shenker algorithm
* [[Count-Min sketch]]
* Sticky sampling
* [[Lossy Count Algorithm|Lossy counting]]
* Sample and Hold
* Multi-stage [[Bloom filter]]s
* Count-sketch
* Sketch-guided sampling
* [[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 average]]s and variance for normalization.<ref>{{Cite conference | doi = 10.1145/2623330.2623740| title = SigniTrend: scalable detection of emerging topics in textual streams by hashed significance thresholds| conference = Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '14| pages = 871–880| year = 2014| last1 = Schubert | first1 = E. | last2 = Weiler | first2 = M. | last3 = Kriegel | first3 = H. P. | authorlink3 = Hans-Peter Kriegel| isbn = 9781450329569}}</ref>

===Counting distinct elements===

Counting the number of distinct elements in a stream (sometimes called the
{{math|''F''<sub>0</sub>}} moment) is another problem that has been well studied.
The first algorithm for it was proposed by Flajolet and Martin. In 2010, [[Daniel Kane (mathematician)|Daniel Kane]], [[Jelani Nelson]] and [[David Woodruff]] found an asymptotically optimal algorithm for this problem.<ref>{{Harvtxt|Kane|Nelson|Woodruff|2010}}</ref> It uses {{math|''O''(''ε''<sup>2</sup> + log ''d'')}} space, with {{math|''O''(1)}} worst-case update and reporting times, as well as universal hash functions and a {{mvar|r}}-wise independent hash family where {{math|1=''r'' = Ω(log(1/''ε'') / log log(1/''ε''))}}.

===Entropy===

The (empirical) entropy of a set of frequencies <math>\mathbf{a}</math> is
defined as <math>F_k(\mathbf{a}) = \sum_{i=1}^n
\frac{a_i}{m}\log{\frac{a_i}{m}}</math>, where <math>m = \sum_{i=1}^n a_i</math>.

Estimation of this quantity in a stream has been done by:
* McGregor et al.{{citation needed|date=November 2017}}
* Do Ba et al.{{citation needed|date=November 2017}}
* Lall et al.{{citation needed|date=November 2017}}
* Chakrabarti et al.{{citation needed|date=November 2017}}

===Online learning===
{{main|Online machine learning}}
Learn a model (e.g. a [[statistical classification|classifier]]) by a single pass over a training set.

* [[Feature hashing]]
* [[Stochastic gradient descent]]

<!--

===Wavelets===
===Counting inversions===
===Longest increasing subsequence===
===Graph problems===
Counting triangles

===Natural language summarization===
===Computational geometry===

streaming convex hulls - Hershberger Suri

===MUD model===

-->

==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]].

== See also ==
* [[Data stream mining]]
* [[Data stream clustering]]
* [[Online algorithm]]
* [[Stream processing]]
* [[Sequential algorithm]]

==Notes==
<references/>

==References==
* {{citation
  | title = The space complexity of approximating the frequency moments
  | last1=Alon | first1=Noga | author1-link = Noga Alon
  | last2=Matias | first2=Yossi | author2-link = Yossi Matias
  | last3=Szegedy | first3=Mario | author3-link = Mario Szegedy
  | year = 1999
  | doi=10.1006/jcss.1997.1545
  | journal = [[Journal of Computer and System Sciences]]
  | volume = 58
  | issue = 1
  | issn = 0022-0000
  | pages = 137&ndash;147}}. First published as {{citation
  | contribution = The space complexity of approximating the frequency moments
  | last1=Alon | first1=Noga
  | last2=Matias | first2=Yossi
  | last3=Szegedy | first3=Mario
  | doi=10.1145/237814.237823
  | year = 1996
  | title = Proceedings of the 28th ACM Symposium on Theory of Computing (STOC 1996)
  | isbn = 978-0-89791-785-8
  | pages = 20&ndash;29| title-link=Symposium on Theory of Computing | citeseerx=10.1.1.131.4984 }}.
* {{citation
  | contribution = Models and issues in data stream systems
  | last1 = Babcock | first1=Brian
  | last2 = Babu | first2=Shivnath
  | last3 = Datar | first3= Mayur
  | last4 = Motwani | first4=Rajeev | author4-link = Rajeev Motwani
  | last5 = Widom | first5=Jennifer | author5-link = Jennifer Widom
  | url = http://infolab.usc.edu/csci599/Fall2002/paper/DML2_streams-issues.pdf
  | doi = 10.1145/543613.543615 | pages = 1–16
  | title= Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2002)
  | year = 2002| isbn = 978-1581135077 | citeseerx = 10.1.1.138.190 }}.
* {{citation
  | title = Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
  | last1=Gilbert|first1=A. C. |author1-link= Anna C. Gilbert
  | last2=Kotidis|first2=Y. 
  | last3=Muthukrishnan|first3=S. 
  | last4=Strauss|first4=M. J.
  | url = http://www.vldb.org/conf/2001/P079.pdf
  | journal = Proceedings of the International Conference on Very Large Data Bases
  | pages = 79&ndash;88
  | year = 2001}}.
* {{citation | last1 = Kane | first1 = Daniel M.
 | last2 = Nelson | first2 = Jelani 
 | last3 = Woodruff | first3 = David P.
 | title = An optimal algorithm for the distinct elements problem
 | booktitle = Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
 | series = PODS '10
 | year = 2010
 | isbn = 978-1-4503-0033-9
 | pages = 41&ndash;52
 | doi = 10.1145/1807085.1807094
 | publisher = ACM
 | location = New York, NY, USA
| citeseerx = 10.1.1.164.142
 }}.
* {{citation
  | title = A simple algorithm for finding frequent elements in streams and bags
  | last1=Karp|first1=R. M. | author1-link = Richard Karp
  | last2=Papadimitriou|first2=C. H. | author2-link = Christos Papadimitriou
  | last3=Shenker|first3=S. | author3-link = Scott Shenker
  | year = 2003
  | volume = 28 | issue = 1 | pages = 51–55 | doi = 10.1145/762471.762473
  | journal = ACM Transactions on Database Systems| citeseerx=10.1.1.116.8530}}.
* {{citation
 |contribution = Data streaming algorithms for estimating entropy of network traffic
 |last1        = Lall
 |first1       = Ashwin
 |last2        = Sekar
 |first2       = Vyas
 |last3        = Ogihara
 |first3       = Mitsunori
 |last4        = Xu
 |first4       = Jun
 |last5        = Zhang
 |first5       = Hui
 |title        = Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS 2006)
 |pages        = 145
 |doi          = 10.1145/1140277.1140295
 |url          = ftp://ftp.cs.rochester.edu/pub/papers/theory/05.tr886.Data_streamg_algms_for_estimating_entropy_of_network_traffic.pdf
 |year         = 2006
|isbn        = 978-1595933195
 |hdl        = 1802/2537
 }}{{Dead link|date=June 2018 |bot=InternetArchiveBot |fix-attempted=no }}.
* {{citation
  | title = A Tutorial on Network Data Streaming
  | last1 = Xu | first1=Jun (Jim)
  | url = http://www.cc.gatech.edu/%7Ejx/reprints/talks/sigm07_tutorial.pdf
  | year = 2007}}.
* 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
* {{citation
  | title = Counting large numbers of events in small registers
  | last1 = Morris | first1 = Robert
  | url = http://dl.acm.org/citation.cfm?id=359627
  | year = 1978
  | volume = 21 | issue = 10 | pages = 840–842 | doi = 10.1145/359619.359627
  | journal = Communications of the ACM}}.

[[Category:Streaming algorithms]]