Count-Min Sketch Data Structure

Data structure is the core of any software program. Without an appropriate data structure, any algorithm might suffer in accessing stored data and optimizing the running time. For example, the following tasks that need to build for a best timing in a data set:

• To estimates frequencies of particular elements
• To finds top-K most frequent elements
• To performs a range of queries
• To make a percentiles estimation. 

As we can see, they are all related to a frequency or a range of queries in a data set. So, one of the structures sets up to get the best optimization for the tasks above is Count-Min Sketch, a method estimates frequency-related properties of a data set.

What is Count-Min Sketch Data Structure?
Count-Min Sketch is one of members in the family of memory efficient data structures to optimize the counting of the rate of an element in its lifetime.

Problem statement:
We have a set of duplicated values, and the issues is to estimate the frequency for each value. The estimation for relatively rare values can be imprecise, however, frequent values and their absolute frequencies should be determined accurately.

The basic idea of Count-Min Sketch:
As similar to Linear Counting, Count-Min sketch is designed as:

• A 2-D array (d x w) of integer counters.
• When a value is set, it is mapped to one position at each of d rows using d difference and an independent hash code.
• Counters on each position will increase for the next arriving values.
• Algorithm estimates the frequency of given value as a minimum of the corresponding counters in each row.

Below is an animation for Count-Min sketch data structure:

Below is a practical implementation of Count-Min sketch:
 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class CountMinSketch {     long estimators[][] = new long[d][w]   // d and w are design parameters     long a[] = new long[d]     long b[] = new long[d]     long p      // hashing parameter, a prime number. For example 2^31-1     void initialize() {         for(i = 0; i < d; i++) {             a[i] = random(p)    // random in range 1..p             b[i] = random(p)         }     }     void add(value) {         for(i = 0; i < d; i++)             estimators[i][ hash(value, i) ]++     }     long estimate(value) {         long minimum = MAX_VALUE         for(i = 0; i < d; i++)             minimum = min(                 minimum,                 estimators[i][ hash(value, i) ]             )         return minimum     }     hash(value, i) {         return ((a[i] * value + b[i]) mod p) mod w     } }

Accuracy

Accuracy of the Count-Min sketch depends on the ratio between the sketch size and the total number inserting values (not duplicated values). This means that Count-Min technique provides significant memory gains only for skew values, for example, the values have very different probabilities.


It is clear that Count-Min sketch can't track frequencies of 5900 elements using only 152 counters, in the case of low skewed values with high frequencies, so the histogram will be very inaccurate.

In general, the applicability of Count-Min sketches is not a straightforward question that can be recommended in the real life of experimental evaluation, but it can be use for some particular cases. However, the theory of Count-Min sketch is a base for accuracy on skewed data and measurements on a real data set.


References:
1. Count-Min Sketch
http://en.wikipedia.org/wiki/Count–min_sketch

2. Streaming Algorithms and Sketches
http://blog.aggregateknowledge.com/tag/count-min-sketch/

3. Count-min sketch & its applications
https://sites.google.com/site/countminsketch/