Count-Min Sketch

In the Russian original of “War and Peace” «Пьер» (Pierre) occurs 1390 times, «Наташа» (Natasha) 827, «Аустерлиц» (Austerlitz) 3. To know the frequency of each word you need a dictionary of all 47,585 distinct words. And what if the words are addresses in network traffic, and there are billions of distinct ones? The Count-Min Sketch keeps a fixed table of counters, hands words out to cells by hashes, and answers with a minimum. Below, the first 100,000 words of the novel go into a table of four rows. Choose a word: its four cells light up, and you can see how much in each is truth and how much belongs to others.

Each of Pierre's cells holds the word’s true occurrences plus all the words that this row's hash put in the same place. The noise differs from row to row: the rows hash independently. The answer is the least polluted cell, the minimum. It is never below the truth and gets closer to it the wider the table: with 256 cells per row Pierre gets +269 on top of the true 208, with 1024 only +29.

The idea

A table of d rows of w counters and d independent hash functions, one per row. An item arrives: in each row add 1 to its cell. A frequency is asked for: take the minimum of its d cells. Each cell equals the truth plus the sum of other items that landed in the same place, so the error is only upwards; the minimum picks the row with the fewest others.

This is a relative of the Bloom filter: there the cells are bits and the question is “was the item there”, here the cells are counters and the question is “how many times”. Both have a one-sided error: the filter may say “was there” about an item that was not, and the sketch may overestimate a frequency, but never underestimates it.

How much it errs

Hence the rule for choosing the sizes. If you want an error of at most ε·N with probability 1 − δ, take w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉. Note that the error is measured from the length of the whole stream N, not from the word's frequency. For a word that occurs a thousand times, an extra fifty is five percent; for a word that occurred three times it is twenty times the truth. Here are all the words of the novel at once:

Frequent words lie on the diagonal: their noise is smaller than they are. Rare ones hang in a horizontal band at the height of the noise, and for them the sketch is useless: with 32 KB and four rows, each of the 36 thousand words seen at most three times is overestimated at least twofold. The guarantee holds with room to spare: one word of 47,585 is above the dashed line e·N/w, although the theorem allows 1.8 %. Hence the main rule of use: Count-Min is good for frequent items, “heavy” queries, addresses, words, and no good for counting rare ones.

Conservative update

The plain sketch adds 1 to all of an item's cells, although the estimate needs only the smallest. Conservative update, devised by Cristian Estan and George Varghese for counting network traffic, raises each of the item's cells only up to “current estimate + 1”, and leaves alone the ones already larger. The truth is still below all the cells, and there is less noise: turn it on in the first scene and look at the rare words. The price is that sketches can no longer be added cell by cell or subtracted: the result depends on the order of the stream. Both versions side by side are the first problem at the end of the article.

The most frequent items

The sketch answers the question about any item, but does not itself remember which items there were. To find the most frequent ones, a heap of k candidates is added: after each item look at its estimate, and if it is greater than the smallest in the heap, put the item there. On “War and Peace” the ten most frequent words by the sketch match the real ones exactly, «и» (“and”), «в» (“in”), «не» (“not”), «что» (“that”), «он» (“he”), because their frequencies are tens of times larger than the noise.

There is also a deterministic way without hashes for this problem, the Misra–Gries algorithm. It keeps k word counters and, when they are all taken and a new word arrives, decreases them all by one. Every word occurring more than n/(k + 1) times is guaranteed to stay in the counters, and its counter is underestimated by at most n/(k + 1). That is the second problem.

Code

A 4 × 2048 sketch, 32 KB of counters, on the whole text of the novel. There are not four hashes per row but two: d hashes are obtained from two as h₁ + i·h₂. Adam Kirsch and Michael Mitzenmacher showed in 2006 that for the Bloom filter this trick hardly worsens the accuracy, and in the sketch it works just as well.

Pierre and Natasha are overestimated by 3–8 %, Austerlitz 24 times: 72 instead of 3. Not a single exact estimate: with 47,585 words over 8192 cells, each cell holds six words on average. The median error is +55, and the guarantee promises at most +579 for all but 1.8 % of the words; in fact one word is above the bound. And the top ten did not move.

What it costs

An addition and a query are d hashes and d memory accesses, O(d). Memory is d·w counters, independent of both the length of the stream and the number of distinct items: with ε = 0.1 % and δ = 1 % that is 2719 × 5 counters, about 53 KB, for any stream. Sketches with the same hashes add cell by cell, giving the sketch of the union of streams, and subtract, if part of a stream has to be removed; this is how they are collected from different servers and for different days.

Where it is used

Networks. A router needs to know which addresses send the most traffic, and a counter per address cannot be kept: there are millions of them, while memory at line rate is kilobytes. The “heavy flows” problem became one of the main ones for the sketch, and conservative update came from exactly here.

Data. In Apache Spark a Count-Min sketch is built over a table column with one function. Redis has the commands CMS.INCRBY and CMS.QUERY in its probabilistic structures module, next to the Bloom filter and HyperLogLog.

What is popular in a stream. Frequent search queries, hashtags, products: a sketch with a heap answers “what is on top right now” without keeping a full count.

History

The sketch was described by Graham Cormode and S. Muthukrishnan in 2004; the journal version came out in 2005 under the title “An improved data stream summary: the count-min sketch and its applications”. A similar structure with counting and a minimum had appeared earlier, as the counting Bloom filter of Fan, Cao, Almeida and Broder in 2000 and in the work of Estan and Varghese in 2002, but it was Cormode and Muthukrishnan who gave simple guarantees through e/ε and ln(1/δ) and showed how many stream problems one table solves.

Problems

In the first problem you keep two sketches on one stream, plain and conservative, on the words of “War and Peace”. In the second, find frequent words with the Misra–Gries algorithm and work out which of them are guaranteed to stay in the counters.