Papers
An Improved Data Stream Summary: The Count-Min Sketch and its Applications
Graham Cormode, S. Muthukrishnan · Journal of Algorithms, vol. 55, pp. 58-75, April 2005 (source read: preprint of 12/16/2003, Elsevier Science), 2005
The problem: summarizing a stream of updates in sublinear space
The paper starts from a vector a of dimension n, which begins at zero and is changed by a stream of pairs (i, c): on each update, the value c is added to position i. At any moment one can ask about functions of this vector. Three queries are central: the point query, which asks for the value of one position; the range query, which asks for the sum of the positions between l and r; and the inner product between two vectors, used, for example, to estimate the size of a join between relations. The authors distinguish the case where updates are always positive (cash register) from the case where they can also be negative (turnstile). The turnstile has two variations: the general case, in which positions can become negative, and the non-negative case, in which the application guarantees that no position falls below zero. Since memory must be much smaller than n, the summary (sketch) can only give approximate answers, with parameters ε and δ: the error stays within a bound with high probability. According to the paper, earlier sketches had limitations: space grew by a factor on the order of 1/ε², many required time linear in the sketch size on each update, they used strongly independent hash functions, and they served a single predefined aggregate. The Count-Min Sketch was proposed to address these limitations: space proportional to 1/ε, update much faster than the sketch size, only pairwise-independent hashing, and use across several queries.
The structure: a matrix of counters and d hash functions
A Count-Min Sketch with parameters (ε, δ) is a matrix of counters with d rows and w columns, all zero at the start. The width is w = ⌈e/ε⌉, where e is the base of the natural logarithm, and the depth is d = ⌈ln(1/δ)⌉. Each row j has its own hash function h_j, which maps an item of the universe {1…n} to a column in {1…w}, drawn from a family of pairwise independent functions. To process the update (i, c), the algorithm adds c to the counter in column h_j(i), in each of the d rows; that is, only d counters are touched, and the update cost depends on d, not on the total size of the matrix. The space is that of w·d counters plus the d hash functions, and each pairwise function can be stored in two words. The name comes from the two operations used in the point query: first count (the accumulated counters) and then compute the minimum across the rows. Different items may fall in the same column of a row, which is called a collision; each counter therefore holds the value of the queried item plus the values of other items that collided with it. This observation is the key to the analysis in the next section. The fact that the matrix is a linear sum of the updates also makes it easy to combine across distributed sites, as the paper notes for sketches in general.
Point query: the minimum across the rows and the error guarantee
To estimate the value a_i in the non-negative case, the algorithm returns the minimum, across the d rows, of the counter in column h_j(i). Theorem 1 states two things: the estimate is never smaller than the true value a_i, and, with probability at least 1 − δ, it does not exceed a_i + ε·||a||₁, where ||a||₁ is the sum of the absolute values of the vector. The error is therefore one-sided, upward. The proof follows the intuition of collisions: in each row, the counter equals a_i plus the sum of the items that collide with i, and, since the updates are non-negative, this excess is never negative, which guarantees that the minimum does not underestimate. With pairwise hashing, the chance of two items colliding in a row is at most ε/e, so the expected excess is at most (ε/e)·||a||₁. By Markov's inequality, the excess exceeds ε·||a||₁ in a row with probability less than 1/e; for the minimum to exceed the bound, all d rows must fail, which happens with probability less than e^(−d), at most δ. The paper highlights that using only Markov, rather than variance with Chebyshev and Chernoff, is what reduces the dependence from 1/ε² to 1/ε and keeps the constants small. The query and update time is O(ln(1/δ)). If values can be negative, the median is used (Theorem 2): the error lies between −3ε·||a||₁ and +3ε·||a||₁, in both directions, but with probability at least 1 − δ^(1/4), a weaker guarantee than in the non-negative case.
Inner product and range queries
For the inner product of two non-negative vectors, a and b, two sketches are kept with the same hash functions. In each row, multiply column by column and sum; the estimate is the minimum across the rows. Theorem 3 says it is never below the true value and, with probability at least 1 − δ, does not exceed it by more than ε·||a||₁·||b||₁, using space O((1/ε)·log(1/δ)). This makes it possible to estimate the size of a join between two relations, with a_i and b_i counting the tuples that have value i in each one. The paper warns that the earlier methods (tug-of-war) gave a guarantee in terms of the L2 norm, which can be much smaller than the L1, but with space on the order of 1/ε². For ranges, writing the query as an inner product with an indicator vector would make the error grow with the size of the range and the cost depend on r − l. Instead, the idea of dyadic intervals, of power-of-2 size, is adopted: log₂ n sketches are kept, one per size, and each update goes into all of them. Any range is covered by at most 2·log₂ n dyadic intervals, each queried as a point query, and the answers are summed. Theorem 4 gives an error of up to 2ε·log n·||a||₁ with probability at least 1 − δ. To obtain an error of ε′·||a||₁, choose ε = ε′/(2·log n), which leads to space O((log²n/ε′)·log(1/δ)).
Applications, comparison with the state of the art, and limits
With the sketch as the basic building block, the paper improves the bounds for two problems. For approximate quantiles in the turnstile model, the binary search for ranges whose sum reaches a fraction of the total now uses Count-Min's range sums in place of Random Subset Sums, and the space drops from a 1/ε² dependence to 1/ε (Theorem 5). For heavy hitters, items with frequency above a fraction φ of the total, in the cash register case the total ||a||₁ is maintained along with a heap of candidates whose estimated value exceeds the threshold. Since the sketch never underestimates, no heavy hitter is missed, and, with probability at least 1 − δ, no item below (φ − ε)·||a||₁ is returned. In the non-negative turnstile case (no count falls below zero), one descends the dyadic hierarchy, splitting the ranges above the threshold, and every item with frequency at least (φ + ε)·||a||₁ is returned, with certainty. The comparison with earlier methods shows that, for point queries, Count Sketch had space on the order of 1/ε², while Count-Min has 1/ε, with update and query in O(log(1/δ)). The paper also acknowledges limits: the estimates depend on the L1 norm, not L2, which makes them less tight for individual queries, and Count-Min is not effective for estimating norms, used in correlations and in counting distinct items; designing sketches as simple as it for those cases is left as an open problem.
See the ideas at work
Practice the designs that use this paper in the System Design school.