3 Streaming Algorithms Great Ideas in Theoretical Computer Science Saarland University, Summer 2014 Some Admin: • Deadline of Problem Set 1 is 23:59, May 14 (today)! • Students are divided into two groups for tutorials. Visit our course website and use Doodle to to choose your free slots. • If you find some typos or like to improve the lecture notes (e.g. add more details, intuitions), send me an email to get .tex file :-) We live in an era of “Big Data”: science, engineering, and technology are producing increasingly large data streams every second. Looking at social networks, electronic commerce, astronomical and biological data, the big data phenomenon appears everywhere nowadays, and presents opportunities and challenges for computer scientists and mathematicians. Comparing with traditional algorithms, several issues need to be considered: A massive data set is too big to be stored; even an O(n2 )-time algorithm is too slow; data may change over time, and algorithms need to cope with dynamic changes of the data. Hence streaming, dynamic and distributed algorithms are needed for analyzing big data. To illuminate the study of streaming algorithms, let us look at a few examples. Our first example comes from network analysis. Any big website nowadays receives millions of visits every minute, and very frequent visit per second from the same IP address are probably generated automatically by computers and due to hackers. In this scenario, a webmaster needs to efficiently detect and block those IPs which generate very frequent visits per second. Here, instead of storing all IP record history which are expensive, we need an efficient algorithm that detect most such IPs. The second example is to quickly obtain statistical information of a massive data set as a preprocessing step to speed-up the runtime of algorithms. Assume that you want to solve a problem in a massive data set (database, graph, etc.), and solving the problem is quite timeconsuming. However, you can get some information by quickly scanning the whole data. For instance, for graph algorithms you want to roughly know if the graph is dense or sparse, if the graph is connected, and so on. This information usually provides statistics of the massive data set, e.g. the frequency of items appearing in the data set, or properties of the set (typically 1 2 Streaming Algorithms graphs), e.g. how well connected the graph is. Although such statistics is not precise for most cases, this approximate information is usually used to speedup subsequent processes. Thees examples motivate the study of streaming algorithms, in which algorithms have access to the input in a certain order, algorithm’s space is limited, and fast approximation is required. 3.1 Model & Basic Techniques A data stream is a sequence of data S = s1 , s2 , . . . , sm , . . . , where each item si belongs to the universe U , where |U | = n. A data streaming algorithm A takes S as input and computes some function f of stream S. Moreover, algorithm A has access the input in a “streaming fashion”, i.e. algorithm A cannot read the input in another order and for most cases A can only read the data once. Depending on how items in U are expressed in S, there are two typical models [20]: 1. Cash Register Model: Each item si in stream S is an item of U . Different items come in an arbitrary order. 2. Turnstile Model: In this model we have a multi-set D, and D = ∅ initially. Every coming item is associated with one of two special symbols in order to indicate the dynamic changes of the data set. For instance, every item in S can be a pair (x, U ), and x is added into D if U is “+”, and x is deleted from D if U is “−”. The turnstile model captures most practical situations that the dataset may change over time. Recent references also call this model dynamic streams. Typically, the size of the universe U is a huge number, and storing the whole data and computing the exact value of f is computationally expensive. Hence the goal is to design sublinear-space algorithms which give a good approximation of f for most cases. Formally, our goal is to design an algorithm A with the following two constraints: • Space: Space of algorithm A is O(poly log(n)). • Quick update time: For every coming item in the stream, quick update time is desired. • Approximate: For confidence parameter ε > 0 and approximation parameter δ > 0, the output of A achieves a (1 ± ε)-approximation of the exact value f (S) with probability at least 1 − δ. That is, the output f ? (S) satisfies Pr [ f ? (S) ∈ [(1 − ε)f (S), (1 + ε)f (S)] ] ≥ 1 − δ. Remark 3.1. Another widely studied model is called the semi-streaming model. In the semistreaming model algorithms run in O(n · poly log n) space, and typically graph streaming algorithms are studied in the semi-streaming model. Note that O(n · poly log n) space allows an algorithm to store all nodes which take O(n log n) bits of space, but storing the whole graph is impossible for dense graphs. 3.2. Hash Functions 3 Basic Techniques. Sampling and sketching are two basic techniques for designing streaming algorithms. The idea behind sampling is easy to state. Every arriving item is retained with a certain probability, and only a subset of the data is retained for further computation. Sampling is easy to implement, and has wide applications. Sketching is the other technique for designing streaming algorithms. A sketch-based algorithm A creates a compact synopsis of the data which has been observed, and the size of the synopsis is vastly smaller than the full observed data. Each update observed in the stream potentially causes this synopsis to be updated, so that the synopsis can be used to approximate certain functions of the data seen so far. Figure 3.1 shows one example of sketches. Durand and Flajolet [12] proposed the LogLog sketch in 2003, which is used to estimate the number of distinct items in a data set. Based on the LogLog sketch, they condense the whole of Shakespear’s works to a table of 256 “small bytes” of 4 bits each. The estimate of the number of distinct words by the LogLog sketch here is 30897, while the true answer is 28239. I.e., a relative error is +9.4%. ghfffghfghgghggggghghheehfhfhhgghghghhfgffffhhhiigfhhffgfiihfhhh igigighfgihfffghigihghigfhhgeegeghgghhhgghhfhidiigihighihehhhfgg hfgighigffghdieghhhggghhfghhfiiheffghghihifgggffihgihfggighgiiif fjgfgjhhjiifhjgehgghfhhfhjhiggghghihigghhihihgiighgfhlgjfgjjjmfl Figure 3.1: The table above condenses the whole of Shakespear’s works. The estimate of the number of distinct words by the LogLog sketch here is 30897, while the true answer is 28239. I.e., a relative error is +9.4%. Notations. We list basic notations used in this lecture. For any integer M , let [M ] , {0, . . . , M − 1}. For any set X, x ∼R X stands for choosing x uniformly at random from set X. 3.2 Hash Functions Most data streaming algorithms rely on constructions of a class of functions, called hash functions, that have found a surprising large number of applications. The basic idea behind using hash functions is to make input date have certain independence through some easy-tocompute function. Formally, we want to construct a family of functions H = {h | h : N 7→ M } such that (1) every function h ∈ H is easy to represent; (2) for any x ∈ N , h(x) is easy to evaluate; (3) for any set S of small cardinality, hashed values of items in S have small collisions. Recall that a set of random variables X1 , . . . , Xn is k-wise independent if, for any index set J ⊂ {1, . . . , n} with |J| ≤ k and for any values xi , i ∈ J, it holds that  Pr   \ i∈J Xi = xi  = Y Pr [ Xi = xi ] . i∈J In particular, the random variables X1 , . . . , Xn are said to be pairwise independent if they are 4 Streaming Algorithms 2-wise independent. That is, for any i, j and values x, y, it holds that     Pr (Xi = x) ∩ (Xj = y) = Pr [ Xi = x ] Pr Xj = y . Hash functions with similar properties are called k-wise independent and pairwise independent hash functions, respectively. Definition 3.2 (Pairwise Independent Hash Functions). A family of functions H = {h | h : N 7→ M } is pairwise independent if the following two conditions hold: 1. ∀x ∈ N , the random variable h(x) is uniformly distributed in M , where h ∼R H, 2. ∀x1 6= x2 ∈ N , the random variables h(x1 ) and h(x2 ) are independent, where h ∼R H. These two conditions state that for any different x1 6= x2 ∈ N , and any y1 , y2 ∈ M , it holds that 1 Prh∼R H [ h(x1 ) = y1 ∩ h(x2 ) = y2 ] = , |M |2 where the probability above is over all random choices of a function from H. Theorem 3.3. Let p be a prime number, and let ha,b = (ax + b) mod p. Define H = {ha,b | 0 ≤ a, b ≤ p − 1}. Then H is a family of pairwise independent hash functions. Proof. We need to show that, for any two different x1 , x2 ∈ N and any two y1 , y2 , it holds that 1 Prh∼R H [ h(x1 ) = y1 ∩ h(x2 ) = y2 ] = 2 . (3.1) p For any a, b, the conditions that ha,b (x1 ) = y1 and ha,b (x2 ) = y2 yield two equations ax1 + b = y1 mod p, and ax2 + b = y2 mod p. Such system has a unique solution of a and b, out of p2 possible pairs of (a, b). Hence (3.1) holds, and H is a family of pairwise independent hash functions. 3.3 Counting Distinct Elements Our first problem is to approximate the Fp -norm of items in a stream. We first define the Fp -norm. Definition 3.4 (Fp -norm). Let S be a multi-set, where every item i of S is in [N ]. Let mi be the number of occurrences of item i in set S. Then the Fp -norm of set S is defined by Fp , X |mi |p , i∈[N ] where 0p is set to be 0. By definition, the F0 -norm of set S is the number of distinct items in S, and the F1 -norm of S is the number of items in S. In this lecture we focus on approximating F0 . 3.3. Counting Distinct Elements 5 Problem 3.5. Let S be a data stream representing a multi set S. Items of S arrive consecutively and every item si ∈ [n]. Design a streaming algorithm to (ε, δ)-approximate the F0 -norm of set S. 3.3.1 The AMS Algorithm Algorithm. The first algorithm for approximating F0 is by Noga Alon, Yossi Matias, and Mario Szegedy [4], and most references use AMS to name their algorithm. The intuition behind their algorithm is quite simple. Assume that we have seen sufficiently many numbers, and these numbers are uniformly distributed. We look at the binary expression Binary(x) of every item x, and we expect that for one out of d distinct items Binary(x) ends with d consecutive zeros. More generally, let ρ(x) , max{i : x mod 2i = 0} i be the number of zeros that Binary(x) ends with, and we have the following observation: • If ρ(x) = 1 for any x, then it is likely that the number of distinct integers is 21 = 2. • If ρ(x) = 2 for any x, then it is likely that the number of distinct integers is 22 = 4. • If ρ(x) = 3 for any x, then it is likely that the number of distinct integers is 23 = 8. • If ρ(x) = r for any x, then it is likely that the number of distinct integers is 2r . To implement this idea, we use a hash function h so that, after applying h, all items in S are uniformly distributed, and on average one out of F0 distinct numbers hit ρ(h(x)) ≥ log F0 . Hence the maximum value of ρ(h(x)) over all items x in the stream could give us a good approximation of the number of distinct items. Algorithm 3.1 An Algorithm For Approximating F0 5: Choose a random function h : [n] → [n] from a family of pairwise independent hash functions; z ← 0; while an item x arrives do if ρ(h(x)) > z then z ← ρ(h(x)); 6: Return 2z+1/2 1: 2: 3: 4: Analysis. Now we analyze Algorithm 3.1. Our goal is to prove the following statement. Theorem 3.6. By running Θ(log(1/δ)) independent copies of Algorithm 3.1 and returning the medium value, we achieve an (O(1), δ)-approximation of the number of distinct items in S. 6 Streaming Algorithms Proof. Let Xr,j be an indicator random variable such that Xr,j = 1 iff ρ(h(j)) ≥ r. Let Yr = P ? j∈S Xr,j be the number of items j such that ρ(h(j)) ≥ r, and z be the value of z when the algorithm terminates. Hence, Yr > 0 iff z ? ≥ r. Since h is pairwise independent, h(j) is uniformly distributed, and E[Xr,j ] = Pr [ ρ(h(j)) ≥ r ] = Pr [ h(x) mod 2r = 0 ] = 1 . 2r By linearity of expectation, we have E[Yr ] = X E[Xr,j ] = j∈S F0 , 2r and Var[Yr ] = X Var[Xr,j ] ≤ j∈S X 2 E[Xr,j ]= j∈S X E[Xr,j ] = j∈S F0 . 2r By using the Markov’s Inequality and Chebyshev’s Inequality, we have Pr [ Yr > 0 ] = Pr [ Yr ≥ 1 ] ≤ F0 E[Yr ] = r, 1 2 and Pr [ Yr = 0 ] ≤ Pr [ |Yr − E[Yr ]| ≥ F0 /2r ] ≤ Let F ? be the output of the algorithm. Then F ? = 2z such that 2a+1/2 ≥ 3F0 . Then Var[Yr ] 2r ≤ . (F0 /2r )2 F0 ? +1/2 . Let a be the smallest integer √ F0 2 . Pr [ F ≥ 3F0 ] = Pr [ z ≥ a ] = Pr [ Ya > 0 ] ≤ a ≤ 2 3 ? ? Similarly, let b be the largest integer such that 2b+1/2 ≤ F0 /3. We have ? ? Pr [ F ≤ F0 /3 ] = Pr [ z ≤ b ] = Pr [ Yb+1 √ 2b+1 2 = 0] ≤ . ≤ F0 3 Running k = Θ(log(1/δ)) independent copies of Algorithm 3.1 above and returning the median value, we can make the two probabilities above at most δ. This gives an (O(1), δ)approximation of the number of distinct items over the stream. 3.3.2 The BJKST Algorithm Our second algorithm for approximating F0 is a simplified version of the algorithm by BarYossef et al. [5]. In contrast to the AMS algorithm, the BJKST algorithm uses a set to keep the sampled items. By running Θ(log(1/δ)) independent copies in parallel and returning the medium of these outputs, the BJKST algorithm (ε, δ)-approximates the F0 -norm of the multiset S. The basic idea behind the sampling scheme of the BJKST algorithm is as follows: 1. Let B be a set that is used to retain sampled items, and B = ∅ initially. The size of B is O(1/ε2 ) and only depends on approximation parameter ε. 3.3. Counting Distinct Elements 7 2. The initial sampling probability is 1, i.e. the algorithm keeps all items seen so far in B. 3. When the set B becomes full, shrink B by removing about half items and from then on the sample probability becomes smaller. 4. In the end the number of items in B and the current sampling probability are used to approximate the F0 -norm. A simplified version of the BJKST algorithm is presented in Algorithm 3.2, where c is a constant. Algorithm 3.2 The BJKST Algorithm (Simplified Version) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: Choose a random function h : [n] → [n] from a family of pairwise independent hash functions z←0 . z is the index of the current level B←∅ . Set B keeps sampled items while an item x arrives do if ρ(h(x)) ≥ z then B ← B ∪ {(x, ρ(h(x)))} while |B| ≥ c/ε2 do . Set B becomes full z ←z+1 . Increase the level shrink B by removing all (x, ρ(h(x))) with ρ(h(x)) < z Return |B| · 2z 3.3.3 Indyk Algorithm Algorithm 3.1 and Algorithm 3.2 work in the cash register model, and cannot handle deletions of items. We next show that F0 -norm of a set S can be estimated in dynamic streams. This algorithm, due to Piotr Indyk [13], presents beautiful applications of the so-called stable distributions in designing streaming algorithms. Problem 3.7. Let S be a stream consisting of pairs of the form (si , Ui ), where si ∈ [n] and Ui = +/− represents dynamic changes of si . Design a data streaming algorithm that, for any ε and δ, (ε, δ)-approximates the F0 -norm of S. Stable Distributions. An important property of Gaussian random variables is that the sum of two of them is again a Gaussian random variable. One consequence of this fact is that if X is Gaussian, then for independent copies of X, expressed by X1 and X2 , and any a, b ∈ N, aX1 + bX2 has the same distribution as cX + d for some positive c and some d ∈ R, i.e. the shape of X is preserved. One class of distributions with similar properties was characterized by Paul Lévy in 1920s when he studies sums of independent identically distributed terms. Informally, a random variable is stable if for independent copies of a random variable X, expressed by X1 , X2 , there are positive constants c, d such that aX1 + bX2 has the same 8 Streaming Algorithms distribution as cX + d. A generalization of this stable property allows us to define p-stable distributions for parameter p ∈ (0, 2]. Definition 3.8 (Stable Distribution). Let p ∈ (0, 2]. A distribution D over R is called p-stable, if for any a1 , . . . , an ∈ R, and independent and identically distributed random variables P X1 , . . . , Xn with distribution D, the random variable i ai Xi has the same distribution as P the random variable ( i |ai |p )1/p X, where X is a random variable with distribution D. Remark 3.9. Such distributions exist for any p ∈ (0, 2]. However, except for p = 1/2, 1, 2, we have not found closed formulae of their density functions and their distributions are defined with respect to their characteristic functions. That is, distribution D is p-stable if a random variable p X with distribution Dp satisfies E[eitX ] = e−|t| . When p = 1/2, 1 or 2, closed formulae of the density functions are known. Actually, they are Lévy distribution, Cauchy distribution, and Gaussian distributions, respectively. Although closed formulae of density functions of general p-stable distributions are unknown, such distribution for any p ∈ (0, 2] can be generated easily as follows [7]: (i) Pick Θ uniformly at random from [−π/2, π/2], and pick r uniformly at random from [0, 1]. (ii) Output sin(pΘ) · cos1/p (Θ) cos(Θ(1 − p)) − ln r !(1−p)/p (3.2) . For detailed discussion of stable distributions, see [3]. Reference [8] gives a short and interesting introduction to stable distributions in designing streaming algorithms. Indyk Algorithm. Algorithm 3.3 gives an idealized algorithm for estimating Fp -norm for any p ∈ (0, 2]. The basic setting is as follows: Assume that every item in the stream is in [n], and we want to achieve an (ε, δ)-approximation of the Fp -norm. Let us further assume that we have matrix M of k , Θ(ε−2 log(1/δ)) rows and n columns, where every item in M is a random variable drawn from a p-stable distribution, generated by (3.2). Given matrix M, Algorithm 3.3 keeps a vector z ∈ Rk which can be expressed by a linear combination of columns of matrix M. Let us prove that this idealized algorithm gives an (ε, δ)-approximation of the Fp -norm. Lemma 3.10. The F0 norm of multi-set S can be approximated by Algorithm 3.3 for choosing sufficiently small p, assuming that we have an upper bound K of the number of occurrences of every item in the stream. Proof. Let M·,j be the jth column of matrix M. Then the vector z in Algorithm 3.3 can be written as X z= mj · M·,j , j∈S where mj is the number of occurrences of item j. Hence zi = j∈S mj · Mi,j . Since Mi,j P is drawn from the p-stable distribution, zi = j∈S mj · Mi,j has the same distribution as P 3.3. Counting Distinct Elements 9 Algorithm 3.3 Approximating Fp -norm in a Turnstile Stream (An Idealized Algorithm) while 1 ≤ i ≤ k do zi ← 0 while an operation arrives do if item j is added then for i ← 1, k do zi ← zi + M[i, j] 1: 2: 3: 4: 5: 6: if item j is deleted then for i ← 1, k do zi ← zi − M[i, j] 7: 8: 9: if Fp -norm is asked then Return medium1≤i≤k {|zi |p } · scalefactor(p) 10: 11: P j∈S |mj |p 1/p . Note that P F0 = X j∈S j∈S |mj |p = Fp , and |mj |0 ≤ X |mj |p = Fp ≤ K p · j∈S X |mj |0 , j∈S where the last inequality holds by the fact that |mj | ≤ K for all j. Hence by setting p ≤ log(1 + ε)/ log K ≈ ε/ log K, we have that Fp ≤ (1 + ε) X |mi |0 = (1 + ε) · F0 . i This idealized algorithm relies on matrix M of size k × n, and for every occurrence of item i, the algorithm needs the ith column of matrix M. However, sublinear space cannot store the whole matrix! So we need an effective way to generate this random matrix such that (1) every entry of M is random and generated according to the p-stable distribution, and (2) each column can be reconstructed when necessary. To construct such matrix M, we use Nisan’s pseudorandom generators1 . Specifically, when the column indexed by i is required, Nisan’s generator takes i as the input and, together with the original see, outputs a sequence of pseudorandom numbers. Based on two consecutive pseudorandom numbers, we use (3.2) to generate one random variable. The theorem below gives the space complexity of Algorithm 3.3. See [9, 13] for the correctness proof. Theorem 3.11. For any parameters ε, δ, there is an algorithm (ε, δ)-approximates the number of distinct elements in a turnstile stream. The algorithm needs O(ε−2 log n log(1/δ)) bits of space. The update time for every coming item is O(ε−2 log(1/δ)). 1 We will discuss Nisan’s pseudorandom generators (PRG) in later lectures, but at the moment you can consider a PRG as a deterministic function f : {0, 1}n 7→ {0, 1}m , where m is much larger than n, such that if we use a random number x as input, f (x) looks almost random. I.e., f extends a truly random binary sequence to an “almost” random binary sequence. 10 Streaming Algorithms 3.4 Frequency Estimation A second problem that we study is to estimate the frequency of any item x, i.e. the number of occurrences of any item x. The basic setting is as follows: Let S be a multi-set, and is empty initially. The data stream consists of a sequence of update operations to set S, and each operation is one of the following three forms: • INSERT(S, x), performing the operation S ← S ∪ {x}; • DELETE(S, x), performing the operation S ← S \ {x}; • QUERY(S, x), querying the number of occurrences of x in the multiset S. Problem 3.12 (Frequency Estimation). Design a streaming algorithm to support INSERT,DELETE, and QUERY operations, and the algorithm approximates the frequency of every item in S. Cormode and Muthukrishnan [10] introduced the Count-Min Sketch for this frequency estimation problem. Count-Min Sketch consists of a fixed array C of counters of width w and depth d, as shown in Figure 3.2. These counters are all initialized to be zero. Each row is associated to a pairwise hash function hi , where each hi maps an element from U to {1, . . . , w}. Algorithm 3.4 gives a formal description of update procedures of the Count-Min sketch. Algorithm 3.4 Frequency Estimation 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: d = dlog(1/δ)e w = de/εe while an operation arrives do if Insert(S, x) then for j ← 1, d do C[j, hj (x)] ← C[j, hj (x)] + 1 if Delete(S, x) then for j ← 1, d do C[j, hj (x)] ← C[j, hj (x)] − 1 if the number of occurrence of x is asked then d Return m x , min1≤j≤d C[j, hj (x)] Choosing w and d. For given parameters ε and δ, the width and height of Count-Min sketch is set to be w , de/εe and d , dln(1/δ)e. Hence for constant ε and δ, the sketch only consists of constant number of counters. Note that the size of the Count-Min sketch only depends on the accuracy of the approximation, and independent of the size of the universe. Analysis. The following theorem shows that the Count-Min Sketch can approximate the number of occurrences of any item with high probability. 3.5. Other Problems in Data Streams 11 h1 (x) h2 (x) d = dlog 1δ e h4 (x) h3 (x) w = de/εe Figure 3.2: Count-Min Sketch. ci has the following property: m ci ≥ mi , and with probability Theorem 3.13. The estimator m ci ≤ mi + ε · F1 , where F1 is the first-moment of the multi-set S. at least 1 − δ, m ci ≥ mi . Proof. Clearly for any i ∈ [n] and 1 ≤ j ≤ d, it holds that hj (i) ≥ mi and hence m So it suffices to prove the second statement. Let Xi,j be the number of items y ∈ [n] \ {i} satisfying hj (i) = hj (y). Then C[j, hj (i)] = mi + Xi,j . Since different hash functions are pairwise independent, we have   Pr hj (i) = hj (y) ≤ and E[Xi,j ] ≤ ε e ε 1 ≤ , w e · F1 . By Markov’s inequality we have ci > mi + ε · F1 ] = Pr ∀j : C[j, hj (i)] > mi + ε · F1 Pr [ m     = Pr ∀j : mi + Xi,j > mi + ε · F1  = Pr ∀j : Xi,j > ε · F1  ≤ Pr ∀j : Xi,j > e · E[Xi,j ] ≤ e−d ≤ δ.  3.5  Other Problems in Data Streams We discussed two basic problems in the lecture, these two problems appeared in early references in the community of streaming algorithms. This line of study over the past years has achieved a number of exciting results. Here we select a few problems for which data streaming algorithms work well: • Approximate the number of triangles in a graph [6, 16]. The stream consists of edges of an underlying graph G, the goal is to approximately count the number T3 of triangles in G. This number relates the clustering coefficient, and the connectivity coefficient in a network, and can be used to analyze topologies of networks. Reference [14, 17] give further generalization of this problem for counting arbitrary subgraphs. 12 References • Spectral Sparsification of a graph. The stream consists of edges of an underlying undirected graph G, and the goal is to output a subgraph H of G with suitable weights on edges of H, such that all spectral properties between graph G and H are preserved. Another notable property of graph H is that, for any vertex subset S, the cut value between S and V \ S in H and G are approximately preserved. Spectral sparsification is widely used as a subroutine to solve other graph problems, and problems in solving linear systems. Kelner and Levin [15] give the first data streaming algorithm for constructing spectral sparsification, and their algorithm works in the semi-streaming setting. It is open for constructing spectral sparsifications in the dynamic semi-streaming setting. • Estimating PageRank in graph streams [21]. 3.6 Further Reference There are excellent surveys in data streams. Muthukrishnan [20] gives a general introduction of streaming algorithms and discusses basic algorithmic techniques in designing streaming algorithms. Cormode and Muthukrishnan [11] give the survey of various applications of the Count-Min sketch. McGregor [18] gives a survey for graph stream algorithms. There are also some online resources. The website [1] gives a summary, applications, and implementations of the Count-Min Sketch. The website [2] maintains a list of open questions in data streams which were proposed in the past workshops on streaming algorithms. For a general introduction to Hash functions, we refer the reader to [19]. References [1] Count-Min Sketch & Its Applications. https://sites.google.com/site/countminsketch/. [2] Open questions in data streams. http://sublinear.info/index.php?title=Main_Page. [3] Stable distributions. http://academic2.american.edu/~jpnolan/stable/stable.html. [4] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137–147, 1999. [5] Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In 6th Annual European Symposium (ESA’02), pages 1–10, 2002. [6] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In 25th Symposium on Principles of Database Systems (PODS’06), pages 253–262, 2006. [7] J. M. Chambers, C. L. Mallows, and B. W. Stuck. A method for simulating stable random varialbes. J. Amer. Statist. Assoc., 71:340–344, 1976. [8] Graham Cormode. Stable distributions for stream computations: It is as easy as 0,1,2. In In Workshop on Management and Processing of Massive Data Streams, at FCRC, 2003. [9] Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan. Comparing data streams using hamming norms (how to zero in). In 28th International Conference on Very Large Databases (VLDB’02), pages 335–345, 2002. [10] Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. J. Algorithms, 55(1):58–75, 2005. References 13 [11] Graham Cormode and S. Muthu Muthukrishnan. Approximating data with the count-min sketch. IEEE Software, 29(1):64–69, 2012. [12] Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities (extended abstract). In 11th International Workshop on Randomization and Computation (RANDOM’03), pages 605–617, 2003. [13] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 53(3):307–323, 2006. [14] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In 39th International Colloquium on Automata, Languages, and Programming (ICALP’12), pages 598–609, 2012. [15] Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory Comput. Syst., 53(2):243–262, 2013. [16] Konstantin Kutzkov and Rasmus Pagh. Triangle counting in dynamic graph streams. CoRR, abs/1404.4696, 2014. [17] Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. Approximate counting of cycles in streams. In 19th International Workshop on Randomization and Computation (RANDOM’11), pages 677–688, 2011. [18] Andrew McGregor. Graph stream algorithms: A survey. ~mcgregor/papers/13-graphsurvey.pdf. http://people.cs.umass.edu/ [19] Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. [20] S. Muthukrishnan. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005. [21] Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. Estimating pagerank on graph streams. J. ACM, 58(3):13, 2011.