4.5.1 Linear Counting

Several methods for distinct element counting are variations of the classical idea of Bloom filter. As an example, we discuss L INEAR C OUNTING , due to Whang et al. [ 246 ], which is presented in figure 4.3 .

Parameter D in the initialization is an upper bound on the number of distinct elements d in the stream, that is, we assume that d ≤ D . A hash function between two sets, intuitively, maps every element x in the first set to a “random” element in the second set. The technical discussion on what exactly this means, and how to build “good enough” hash functions that can be stored in few bits is left for section 4.9.1. Let us say only that hash functions that are random enough for our purposes and map {0,… ,m − 1} to itself can be obtained from O (log m ) truly random bits, and stored with O (log m ) bits.

Each item present in the stream sets to 1 an entry of table B , the same one regardless of how many times it occurs. Intuitively, a good hash function ensures that the distinct items appearing in the stream are uniformly allocated to the entries of B . Then, the expected value returned by Query is the number of distinct values seen in the stream plus a tiny bias term, whose standard deviation is . For a reasonably large number of distinct elements this is much smaller than d itself, which means that L INEAR C OUNTING will be pretty accurate in relative terms.

4.5.2 Cohen’s Logarithmic Counter

Cohen’s counter [ 74 ] builds on this idea but moves to logarithmic space using the following observation. The average gap between two consecutive 1s in B is determined by the number of 1 bits in the stream, and is approximately s/d . This is true in particular for the first gap, or equivalently for the position of the first 1. Conveniently, it only takes log s bits to store this first position, because it is the minimum of the observed values of the hash function. The sketch is shown in figure 4.4 . Cohen’s counter only uses log D bits to store p .

It can be shown that the expected value of p is D/d and that the Query procedure returns d in expectation. Its variance is large, roughly ( D/d ) ² . It can be reduced by running several copies in parallel and averaging, but this requires building several independent and “good” hash functions, which is problematic. An alternative method using a single hash function will be presented as part of the next sketch.

4.5.3 The Flajolet-Martin Counter and HyperLogLog

A series of algorithms starting with the Flajolet-Martin counter [ 105 ] and culminating in HyperLogLog [ 104 ], achieve relative approximation 𝜖 with even fewer bits, O ((log log D ) / 𝜖 ² ), plus whatever is required to store a hash function. The intuition of this method is the following: let D be 2 ^k . Select without repetition numbers in the range [0, 2 ^k − 1] uniformly at random; this is what we obtain after applying a good hash function to stream items. All these numbers can be written with k bits in binary; half of these numbers have 0 as the first bit, one-quarter have two leading 0s, one-eighth start with 000, and so on. In general, a leading pattern 0 ⁱ 1 appears with probability 2 ^{−( i +1)} , so if 0 ⁱ 1 is the longest such pattern in the hash values drawn so far, then we may expect d to be around 2 ^{i +1} . Durand and Flajolet [ 93 ], in their improvements of Flajolet-Martin, realized that one only needs to remember k , with log k = log log D bits, to keep track of the longest pattern, or largest i . The basic Flajolet-Martin probabilistic counter with this improvement is given in pseudocode in figure 4.5 .

The method needs a hash function h that transforms each item into an integer between 0 and L − 1, as randomly as possible. It was shown in [ 105 ] that, if d distinct items have been read, the expected value of p is log(0.77351 d ) and its standard deviation is 1.12127… The sketch only requires memory to store p , whose value is at most L = log D , and so requires log log D bits.

The main drawback of this method is the relatively large error in the estimation, on the order of d . It can be reduced by averaging several copies, as discussed before. But this has two problems: one, it multiplies the computation time of the update operation accordingly. Two, obtaining several truly independent hash functions is hard.

Flajolet and Martin propose instead the technique they call stochastic averaging : Conceptually divide the stream into m = 2 ^b substreams, each one feeding a different copy of the sketch. For each item x , use the first b = log m bits of h ( x ) to decide the stream to which x is assigned, and the other m − log m of bits of h ( x ) to feed the corresponding sketch. A single hash function can be used now, because items in different substreams see independent parts of the same function, and update time is essentially the same as for a single sketch. Memory use is still multiplied by m .

Different variants of the algorithm differ in how they combine the results from the m copies into a single estimation.

• LogLog [ 93 ] returns the geometric average of their estimations, which is 2 to the arithmetic average of their variables p , times a constant.
• SuperLogLog [ 93 ] removes the top 30% of the estimations before doing the above; this reduces the effect of outliers.
• HyperLogLog, by Flajolet et al. [ 104 ], returns instead the harmonic average of the m estimations, which also smooths out large outliers.

The variants above achieve standard deviations 1.3 d / , 1.05 d / , and 1.04 d / , respectively, and use memory O ( m log log D ), plus O (log D ) bits to store a hash function that can be shared among all instances of the counter. By using Chebyshev’s inequality, we obtain an ( 𝜖 , δ )-approximation provided that m = O (1/( δ 𝜖 ² )); note that it is not clear how to apply Hoeffding’s bound because the estimation is not an average. Stated differently, taking 𝜖 = O (1/ ), we achieve relative approximation 𝜖 for fixed confidence using O ((log log D ) / 𝜖 ² ) bits of memory.

In more concrete terms, according to [ 104 ], HyperLogLog can approximate cardinalities up to 10 ⁹ within, say, 2% using just 1.5 kilobytes of memory. A discussion of practical implementations of HyperLogLog for large applications can be found in [ 134 ].

4.5.4 An Application: Computing Distance Functions in Graphs

Let us mention a nonstreaming application of the Flajolet-Martin counter, to illustrate that streaming algorithms can sometimes be used to improve time or memory efficiency in nonstreaming problems.

Boldi et al. [ 47 ], improving on [ 192 ], proposed the HyperANF counter, which uses HyperLogLog to approximate the neighborhood function N of graphs. For a node v and distance d , N ( v,d ) is defined as the number of nodes reachable from node v by paths of length at most d . The probabilistic counter allows for a memory-efficient, approximate calculation of N ( .,d ) given the values of N ( .,d − 1), and one sequential pass over the edges of the graph in the arbitrary order in which they are stored in disk, that is, with no expensive disk random accesses.

We give the intuition of how to achieve this. The first key observation is that a vertex is reachable from v by a path of length at most d if it is either reachable from v by a path of length at most d − 1, or reachable by a path of length at most d − 1 from a vertex u such that ( v,u ) is an edge. The second key observation is that HyperLogLog counters are mergeable, a concept we will explore in section 4.8. It means that, given two HyperLogLog counters H _A and H _B that result from processing two streams A and B , there is a way to obtain a new HyperLogLog counter merge ( H _A ,H _B ) identical to the one that would be obtained by processing the concatenation of C of A and B . That is, it contains the number of distinct items in C . Then, suppose inductively that we have computed for each vertex v a HyperLogLog counter H _{d −1} ( v ) that (approximately) counts the number of vertices at distance at most d − 1 from v , or in other words, approximates N ( v,d − 1). Then compute H _d ( v ) as follows:

1. H _d ( v ) ← H _{d −1} ( v ).
2. For each edge ( v,u ) (in arbitrary order) do

Using the first key observation above, it is clear that H _d ( v ) equals N ( v,d ) if the counts are exact; errors due to approximations might in principle accumulate and amplify as we increase d , but experiments in [ 47 ] do not show this effect. We can discard the H _{d −1} counters once the H _d are computed, and reuse the space they used. Thus we can approximate neighborhood functions up to distance d with d sequential scans of the edge database and memory O ( n log log n ).

Using this idea and a good number of clever optimizations, Backstrom et al. [ 21 ] were able to address the estimation of distances in the Facebook graph, the graph where nodes are Facebook users and edges their direct friendship relationships. The graph had 721 million users and 69 billion links. Remarkably, their computation of the average distance between users ran in a few hours on a single machine, and resulted in average distance 4.74, corresponding to 3.74 intermediaries or “degrees of separation.” Informally, this confirms the celebrated experiment by S. Milgram in the 1960s [ 177 ], with physical letters and the postal service, hinting that most people in the world were at the time no more than six degrees of separation apart from each other.

A unified view of sketches for distance-related queries in massive graphs is presented in [ 75 ].

4.5.5 Discussion: Log vs. Linear

More details on algorithms for finding distinct elements can be found in [ 176 ], which also provides empirical evaluations. It focuses on the question of when it is worth using the relatively sophisticated sublinear sketches rather than simple linear counting. The conclusion is that linear sketches are preferable when extremely high accuracy, say below 𝜖 = 10 ⁻⁴ , is required. Logarithmic sketches typically require O (1 / 𝜖 ² ) space for multiplicative error 𝜖 , which may indeed be large for high accuracies.

In data mining and ML applications, relatively large approximation errors are often acceptable, say within 𝜖 = 10 ⁻¹ , because the model mined is the combination of many statistics, none of which is too crucial by itself, and because anyway data is viewed as a random sample of reality. Thus, logarithmic space sketches may be an attractive option.

Also worthy of mention is that [ 144 ] gives a more involved, asymptotically optimal algorithm for counting distinct elements, using O ( 𝜖 ⁻² + log d ) bits, that is, removing the log log d factor in HyperLogLog. HyperLogLog still seems to be faster and smaller for practical purposes.

4.6.1 The S PACE S AVING Sketch

Counter-based algorithms are historically evolutions of a method by Boyer and Moore [ 50 ] to find a majority element (one with frequency at least 1/2) when it exists. An improvement of this method was independently discovered by Misra and Gries [ 179 ], Demaine et al. [ 86 ], and Karp et al. [ 145 ]. Usually called F REQUENT now, this method finds a list of elements guaranteed to contain all 𝜖 –heavy hitters with memory O (1 / 𝜖 ) only.

A drawback of F REQUENT is that it provides the heavy hitters but no reliable estimates of their frequencies, which are often important to have. Other counter-based sketches that do provide approximations of the frequencies include Lossy Counting and Sticky Sampling, both due Manku and Motwani [ 165 , 166 ], and Space Saving, due to Metwally et al. [ 175 ]. We describe Space Saving, reported in [ 80 , 161 , 164 ] to have the best performance among several heavy hitter algorithms. Additionally, it is simple and has intuitive rigorous guarantees on the quality of approximation.

Figure 4.6 shows the pseudocode of S PACE S AVING . It maintains in memory a set of at most k pairs (item, count), initialized with the first k distinct elements and their counts. When a new stream item arrives, if the item already has an entry in the set, its count is incremented. If not, this item replaces the item with the lowest count, which is then incremented by 1. The nonintuitive part is that this item inherits the counts of the element it evicts, even if this is its first occurrence. However, as the following claims show, the error is never too large, and can neither make a rare element look too frequent nor a true heavy hitter look too infrequent.

Let f _t,x be the absolute frequency of item x among the first t stream elements, and if x is in the sketch at time t , let count _t ( x ) be its associated count; we omit the subindex t when it is clear from the context. The following are true for every item x and at all times t :

1. The value of the smallest counter min is at most t/k .
2. If x ∉ S , then f _x ≤ min .
3. If x ∈ S , then f _x ≤ count ( x ) ≤ f _x + min .

(1) and (2) imply that every x with frequency above t/k is in S , that is, the sketch contains all (1 /k )–heavy hitters. (3) says that the counts for elements in S do not underestimate the true frequencies and do not overestimate them by more than t/k . The value t/k can be seen as the minimum resolution: counts are good approximations only for frequencies substantially larger than t/k , and an item with frequency 1 may have just made it into the sketch and have associated count up to t/k .

The Stream-Summary data structure proposed in [ 175 ] implements the sketch, ensuring amortized constant time per update. For every count value c present in the sketch, a bucket is created that contains c and a pointer to a doubly linked list of all the items having count c . Buckets are kept in a doubly linked list, sorted by their values c . The nodes in the linked lists of items all contain a pointer to their parent bucket, and there is a hash table that, given an item, provides a pointer to the node that contains it. The details are left as an exercise.

All in all, taking k = ⌈ 1 / 𝜖 ⌉ , S PACE S AVING finds all 𝜖 –heavy hitters, with an approximation of their frequencies that is correct up to 𝜖 , using O (1 / 𝜖 ) memory words and constant amortized time.

S PACE S AVING , F REQUENT , Lossy Counting, and Sticky Sampling are all deterministic algorithms; they do not use hash functions or randomization, except perhaps inside the hash table used for searching the set. It is easy to adapt S PACE S AVING to updates of the form ( x,c ), where x is an item, c any positive weight, and the pair stands for the assignment f _x ← f _x + c , with no significant impact on memory or update time. But it cannot simulate item deletions or, equivalently, updates with negative weights.

4.6.2 The CM-Sketch Algorithm

The Count-Min sketch or CM-sketch is due to Cormode and Muthukrishnan [ 81 ] and can be used to solve several problems related to item frequencies, among them the heavy hitter problem. Unlike F REQUENT and S PACE S AVING , it is probabilistic and uses random hash functions extensively. More importantly for some applications, it can deal with updates having positive and negative weights, in particular, with item additions and subtractions.

We first describe what the sketch achieves, then its implementation. We consider streams with elements of the form ( x,c ) where x is an item, c any positive or negative weight update to f _x . We use F to denote the total weight at a given time.

The CM-sketch creation function takes two parameters, the width w and the depth d . Its update function receives a pair ( x,c ) as above. Its Query function takes as parameter an item x , and returns a value that satisfies, with probability 1 − δ , that

provided w ≥ ⌈ e / 𝜖 ⌉ and d ≥ ⌈ ln(1 /δ ) ⌉ . This holds at any time, no matter how many items have been added and then deleted before.

We assume from now on that F > 0 for the inequality above to make sense, that is, the negative weights are smaller than the positive weight. Like in S PACE S AVING , this means that is a reasonable approximation of f _x for heavy items, that is, items whose weight is a noticeable fraction of F . Additionally, the memory used by the algorithm is approximately wd counters or accumulators. In summary, values f _x are approximated within an additive factor of 𝜖 with probability 1 − δ using O (ln(1 /δ ) / 𝜖 ) memory words.

Let us now describe the implementation of the sketch. A CM-sketch with parameters w,d consists of a two-dimensional array of counters with d rows and w columns, together with d independent hash functions h ₀ , …, h _{d −1} mapping items to the interval [0… w − 1]. Figure 4.7 shows an example of the CM-sketch structure for d = 4 and w = 7, and figure 4.8 shows the pseudocode of the algorithm.

It can be seen that both Update and Query operations perform O ( d ) operations. We do not formally prove the approximation bounds in inequality ( 4.1 ), but we provide some intuition of why they hold. Observe first that for a row i and column j , A [ i,j ] contains the sum of the weights in the stream of all items x such that h _i ( x ) = j . This alone ensures that f _x ≤ A [ i,h _i ( x )] and therefore that f _x ≤ Query ( x ). But A [ i,h _i ( x )] may overestimate f _x if there are other items y that happen to be mapped to the same cell of that row, that is h _i ( x ) = h _i ( y ). The total weight to be distributed among the w cells in the row is F , so the expected weight falling on any particular cell is F/w . One can show that it is unlikely that any cell receives much more than this expected value. Intuitively, this may happen if a particularly heavy item is mapped in the cell, but the number of heavy items is limited, so this happens rarely; or else if too many light items are mapped to the cell, but this is also unlikely because the hash function places items more or less uniformly among all w cells in the row. Markov’s inequality is central in the proof.

Returning to the heavy hitter problem, the CM-sketch provides a reasonable approximation of the frequency of elements that are heavy hitters, but there is no obvious way to locate them from the data structure. A brute-force search that calls Query ( x ) for all possible x is unfeasible for large item universes. The solution uses an efficient implementation of so-called Range-Sum queries , which are of independent interest in many situations.

A Range-Sum query is defined on sets of items that can be identified with integers in {1, . . . , | I |}. The range-sum query with parameters [ x,y ] returns f _x + f _{x +1} + ⋯ + f _{y −1} + f _y . As an example, consider a router handling packets destined to IP addresses. A range-sum query for the router could be “How many packets directed to IPv4 addresses in the range 172.16.aaa.bbb have you seen?” We expect to solve this query faster than iterating over the 2 ¹⁶ addresses in the range.

Range-sum queries can be implemented using CM-sketches as follows: Let | I | = 2 ⁿ be the number of potential items. For every power of two 2 ⁱ , 0 ≤ i ≤ n , create a CM-sketch C _i that range-sums items in intervals of size 2 ⁱ . More precisely, Query ( j ) to C _i will return the total count of items in the interval [ j 2 ⁱ …( j + 1)2 ⁱ − 1]. Alternatively, we can imagine that at level i each item x belongs to the “superitem” x mod 2 ^{n − i} . In particular, C ₀ stores individual item counts and C _n the sum of all counts. Then we can answer the range-sum query ( x, y ) to C _i , for x and y in the same interval of size 2 ⁱ , with the following recursion: If x and y fall in the same interval of size 2 ^{i −1} , we query ( x, y ) to C _{i −1} and return its answer. If, on the other hand, there is some j such that x < j 2 ^{i −1} ≤ y (that is, x and y do not belong to the same interval of size 2 ^{i −1} ), we ask the range-sum queries ( x, j 2 ^{i −1} − 1) and ( j 2 ^{i −1} , y ) to C _{i −1} , and then return the sum of the answers. Sketch C ₀ is the base of the recursion.

Now, the heavy hitter problem with parameter k can be solved by exploring the set of intervals [ j 2 ⁱ , ( j + 1)2 ⁱ − 1] by depth. If the weight of the interval is below F/k , no leaf below it can be a heavy hitter, so the empty list is returned. Otherwise, it is divided into two equal-size intervals that are explored separately, and the lists returned are concatenated. When a leaf is reached, it is returned if and only if it is a heavy hitter, that is, its weight is F/k or more. Also, at each level of the tree there can be at most k nodes of weight F/k or more, so at most k log | I | nodes of the tree are explored. All in all, heavy hitters are found using O ((log | I |)ln(1 /δ ) / 𝜖 ) memory words.

As already mentioned, the CM-sketch can be used for solving several other problems on streams efficiently [ 81 ], including quantile computations, item frequency histograms, correlation, and the inner product of two streams. For the case of quantile computation, however, the specialized sketch FrugalStreaming [ 163 ] is considered the state of the art. We will describe another quantile summary in section 6.4.3 when describing the management of numeric attributes in classification problems.

4.6.3 CountSketch

The C OUNT S KETCH algorithm was proposed by Charikar et al. [ 64 ]. Like CM- SKETCH , it supports updates with both positive and negative weights. It uses memory O (1 / 𝜖 ² ), but it finds the so-called F ₂ –heavy hitters, which is an interesting superset of the regular heavy hitters, or F ₁ –heavy hitters.

The F ₂ norm of a stream is defined as . Item x is an F ₂ –heavy hitter with threshold 𝜖 if . Some easy algebra shows that every F ₁ –heavy hitter is also an F ₂ –heavy hitter.

In its simplest form, C OUNT S KETCH can be described as follows. It chooses two hash functions. Function h maps items to a set of w buckets {0,… ,w − 1}. Function σ maps items to {−1, +1}. Both are assumed to be random enough. In particular, an important property of σ is that for different x and y , σ ( x ) and σ ( y ) are independent, which means that Pr[ σ ( x ) = σ ( y )] = 1/2, which means that E[ σ ( x ) · σ ( y )] = 0.

The algorithm keeps an array A of w accumulators, initialized to 0. For every pair ( x,c ) in the stream, it adds to A [ h ( x )] the value σ ( x ) · c . Note that updates for a given x are either all added or all subtracted, depending on σ ( x ). When asked to provide an estimation of f _x , the algorithm returns Query ( x ) = σ ( x ) · A [ h ( x )]. This estimation would be exact if no other item y was mapped to the same cell of A as x , but this is rarely the case. Still, one can prove that the expectation over random choices of the hash functions is the correct one. Indeed:

because, as mentioned, E [ σ ( x ) σ ( y )] = 0 for x ≠ y , and σ ( x ) ² = 1. Similar algebra shows that Var( Query ( x )) ≤ F ₂ /w .

Now we can use a strategy like the one described in section 4.9.2 to improve first accuracy, then confidence: take the average of w = 12/(5 𝜖 ² ) independent copies; by Chebyshev’s inequality, this estimates each frequency with additive error and probability 5/6. Then do this d = O (ln(1 /δ )) times independently and return the median of the results; Hoeffding’s inequality shows (see exercise 4.9) that this lifts the confidence to 1 − δ . Therefore, the set of x ’s such that contains each F ₂ –heavy hitter with high probability. Note that, unlike in CM- SKETCH and S PACE S AVING , there may be false negatives besides false positives, because the median rather than the min is used. Memory use is O (ln(1 /δ ) / 𝜖 ² ) words.

At this point, we can view the d copies of the basic algorithm as a single algorithm that resembles CM- SKETCH : it chooses hash functions h ₀ ,… ,h _{d −1} , σ ₀ ,… ,σ _{d −1} , and maintains an array A with d rows and w columns. The pseudocode is shown in figure 4.9 . To recover the heavy hitters efficiently, C OUNT S KETCH also maintains a heap of the most frequent elements seen so far on the basis of the estimated weights.

Improvements of C OUNT S KETCH are presented in [ 51 , 249 ].

As a brief summary of the heavy hitter methods, and following [ 164 ], if an application is strictly limited to discovering frequent items, counter-based techniques such as Lossy Counting or Space Saving are probably preferable in time, memory, and accuracy, and are easier to implement. For example, C OUNT S KETCH and CM- SKETCH were found to be less stable and perform worse for some parameter ranges. On the other hand, hash-based methods are the only alternative to support negative item weights, and provide useful information besides simply the heavy hitters.

4.6.4 Moment Computation

Frequency moments are a generalization of item frequency that give different information on the distribution of items in the stream. The p th moment of a stream where each item x has absolute frequency f _x is defined as

Observe that F ₁ is the length of the stream and that F ₀ is the number of distinct items it contains (if we take 0 ⁰ to be 0, and f ⁰ = 1 for any other f ). F ₂ is of particular interest, as it can be used to compute the variance of the items in the stream. The limit case is F _∞ , defined as

or, in words, the frequency of the most frequent element.

Alon et al. [ 14 ] started the study of streaming algorithms for computing approximations of frequency moments. Their sketch for p ≥ 2 (known as the Alon-Matias-Szegedy or AMS sketch) uses a technique similar to the one in CM- SKETCH : take hash functions that map each item to {−1, +1}, use them to build an unbiased estimator of the moment with high variance, then average and take medians of several copies to produce an arbitrarily accurate estimation.

Their work already indicated that there was an abrupt difference in the memory requirements for computing F _p for p ≤ 2 and for p > 2. After a long series of papers it was shown in [ 141 ] that, considering relative approximations,

• for p ≤ 2, F _p can be approximated in a data stream using O ( 𝜖 ⁻² (log t + log m )ln(1 /δ )) bits of memory, and
• for p > 2, F _p can be approximated in a data stream using bits,

up to logarithmic factors, where t is the length of the stream and m = | I | is the size of the set of items. Furthermore, memory of that order is in fact necessary for every p other than 0 and 1. Later work has essentially removed the logarithmic gaps as well. In particular, for F _∞ or the maximum frequency, linear memory in the length of the stream is required. Observe that for the special cases p = 0 and p = 1 we have given algorithms using memory O (log log t ) rather than O (log t ) in previous sections.

4.9.1 Hash Functions

For several sketches we have assumed the existence of hash functions that randomly map a set of items I to a set B . Strictly speaking, a fully independent hash function h should be such that the value of h on some value x cannot be guessed with any advantage given the values of h on the rest of the elements of I ; formally, for every i ,

But it is incorrect to think of h ( x _i ) as generating a new random value each time it is called—it must always return the same value on the same input. It is thus random, but reproducibly random. To create such an h we can randomly guess and store the value of h ( x _i ) for each x _i ∈ I , but storing h will use memory proportional to | I |log | B |, defeating the goal of using memory far below | I |.

Fortunately, in some cases we can show that weaker notions of “random hash function” suffice. Rather than using a fixed hash function, whenever the algorithm needs to use a new hash function, it will use a few random bits to choose one at random from a family of hash functions H . We say that family H is pairwise independent if for any two distinct values x and y in I and α , β in B we have

where the probability is taken over a random choice of h ∈ H . This means that if we do not know the h chosen within H , and know only one value of h , we cannot guess any other value of h .

Here is a simple construction of a family of pairwise independent hash functions when | I | is some prime p . View I as the interval [0… p − 1]. A function h in the family is defined by two values a and b in [0… p − 1] and computes h ( x ) = ( ax + b ) mod p . Note that one such function is described by a and b , so with 2log p bits. This family is pairwise independent because given x , y and the value h ( y ), for each possible value h ( x ) there is a unique solution ( a, b ) to the system of equations { h ( x ) = ax + b,h ( y ) = ay + b }, so all values of h ( x ) are equally likely. Note however that if we know x , y , h ( x ), and h ( y ), we can solve uniquely for a , b so we know the value h ( z ) for every other input z . If | I | is a prime power p ^b , we can generalize this construction by operating in the finite field of size p ^b ; be warned that this is not the same as doing arithmetic modulo p ^b . We can also choose a prime slightly larger than | I | and get functions that deviate only marginally from pairwise independence.

Pairwise independent functions suffice for the CM-sketch. Algorithms for moments require a generalization called 4-wise independence. For other algorithms, such as HyperLogLog, k -wise independence cannot be formally shown to suffice, to the best of our knowledge. However, although no formal guarantee exists, well-known hash functions such as MD5, SHA1, SHA256, and Murmur3 seem to pose no problem in practice [ 104 , 134 ]. Theoretical arguments have been proposed in [ 71 ] for why simple hash functions may do well on data structure problems such as sketching.

4.9.2 Creating ( 𝜖 , δ )-Approximation Algorithms

Let f be a function to be approximated, and g a randomized algorithm such that E[ g ( x )] = f ( x ) for all x , and Var( g ( x )) = σ ² . Run k independent copies of g , say g ₁ , …, g _k , and combine their outputs by averaging them, and let h denote the result. We have E[ h ( x )] = f ( x ) and, by simple properties of the variance, Var(| f ( x ) − h ( x )|) ≤ Var( f ( x ) − h ( x )) = Var( h ( x )) = σ ² /k . Then by Chebyshev’s inequality we have | f ( x ) − h ( x )| > 𝜖 with probability at most σ ² /( k 𝜖 ² ), for every 𝜖 . This means that h is an ( 𝜖 , δ )-approximation of f if we choose k = σ ² /( 𝜖 ² δ ). The memory and update time of h are k times those of g .

A dependence of the form σ ² / 𝜖 ² to achieve accuracy 𝜖 is necessary in general, but the dependence of the form 1 /δ can be improved as follows: use the method above to achieve a fixed confidence, say, ( 𝜖 , 1/6)-approximation. Then run ℓ copies of this fixed confidence algorithm and take the median of the results. Using Hoeffding’s inequality we can show that this new algorithm is an ( 𝜖 , δ )-approximation if we take ℓ = O (ln(1 /δ )); see exercise 4.9. The final algorithm therefore uses k · ℓ = O (( σ ² / 𝜖 ² ) ln(1 /δ )) times the memory and running time of the original algorithm g .

This transformation is already present in the pioneer paper on moment estimation in streams by Alon et al. [ 14 ].

4.9.3 Other Sketching Techniques

The sketches presented in this chapter were chosen for their potential use in stream mining and learning on data streams. Many other algorithmic problems on data streams have been proposed, for example solving combinatorial problems, geometric problems, and graph problems. Also, streaming variants of deep algorithmic techniques such as wavelets, low-dimensionality embeddings, and compressed sensing have been omitted in our presentation. Recent comprehensive references include [ 79 , 172 ].

Algorithms for linear-algebraic problems deserve special mention, given how prominent they are becoming in ML. Advances in online Singular Value Decomposition ([ 221 ] and the more recent [ 159 ]) and Principal Component Analysis [ 49 ] are likely to become highly influential in streaming. The book [ 248 ] is an in-depth presentation of sketches for linear algebra; their practical use in stream mining and learning tasks is a very promising, but largely unexplored, direction.