We map the input value to multiple points in a relatively small output space. Therefore, the count associated with a given input will be applied to multiple counts in the output space. Even though collisions will occur, the minimum count associated with a given input will have some desirable properties, including the ability to be used to estimate the largest N counts.
http://debasishg.blogspot.com/2014/01/count-min-sketch-data-structure-for.html
Parameters of the sketch:
These parameters are inversely and exponentially (respectively) related to the sketch size parameters, d and w.
In [ ]:
import sys
import random
import numpy as np
import heapq
import json
import time
BIG_PRIME = 9223372036854775783
def random_parameter():
return random.randrange(0, BIG_PRIME - 1)
class Sketch:
def __init__(self, delta, epsilon, k):
"""
Setup a new count-min sketch with parameters delta, epsilon and k
The parameters delta and epsilon control the accuracy of the
estimates of the sketch
Cormode and Muthukrishnan prove that for an item i with count a_i, the
estimate from the sketch a_i_hat will satisfy the relation
a_hat_i <= a_i + epsilon * ||a||_1
with probability at least 1 - delta, where a is the the vector of all
all counts and ||x||_1 is the L1 norm of a vector x
Parameters
----------
delta : float
A value in the unit interval that sets the precision of the sketch
epsilon : float
A value in the unit interval that sets the precision of the sketch
k : int
A positive integer that sets the number of top items counted
Examples
--------
>>> s = Sketch(10**-7, 0.005, 40)
Raises
------
ValueError
If delta or epsilon are not in the unit interval, or if k is
not a positive integer
"""
if delta <= 0 or delta >= 1:
raise ValueError("delta must be between 0 and 1, exclusive")
if epsilon <= 0 or epsilon >= 1:
raise ValueError("epsilon must be between 0 and 1, exclusive")
if k < 1:
raise ValueError("k must be a positive integer")
self.w = int(np.ceil(np.exp(1) / epsilon))
self.d = int(np.ceil(np.log(1 / delta)))
self.k = k
self.hash_functions = [self.__generate_hash_function() for i in range(self.d)]
self.count = np.zeros((self.d, self.w), dtype='int32')
self.heap, self.top_k = [], {} # top_k => [estimate, key] pairs
def update(self, key, increment):
"""
Updates the sketch for the item with name of key by the amount
specified in increment
Parameters
----------
key : string
The item to update the value of in the sketch
increment : integer
The amount to update the sketch by for the given key
Examples
--------
>>> s = Sketch(10**-7, 0.005, 40)
>>> s.update('http://www.cnn.com/', 1)
"""
for row, hash_function in enumerate(self.hash_functions):
column = hash_function(abs(hash(key)))
self.count[row, column] += increment
self.update_heap(key)
def update_heap(self, key):
"""
Updates the class's heap that keeps track of the top k items for a
given key
For the given key, it checks whether the key is present in the heap,
updating accordingly if so, and adding it to the heap if it is
absent
Parameters
----------
key : string
The item to check against the heap
"""
estimate = self.get(key)
if not self.heap or estimate >= self.heap[0][0]:
if key in self.top_k:
old_pair = self.top_k.get(key)
old_pair[0] = estimate
heapq.heapify(self.heap)
else:
if len(self.top_k) < self.k:
heapq.heappush(self.heap, [estimate, key])
self.top_k[key] = [estimate, key]
else:
new_pair = [estimate, key]
old_pair = heapq.heappushpop(self.heap, new_pair)
if new_pair[1] != old_pair[1]:
del self.top_k[old_pair[1]]
self.top_k[key] = new_pair
self.top_k[key] = new_pair
def get(self, key):
"""
Fetches the sketch estimate for the given key
Parameters
----------
key : string
The item to produce an estimate for
Returns
-------
estimate : int
The best estimate of the count for the given key based on the
sketch
Examples
--------
>>> s = Sketch(10**-7, 0.005, 40)
>>> s.update('http://www.cnn.com/', 1)
>>> s.get('http://www.cnn.com/')
1
"""
value = sys.maxint
for row, hash_function in enumerate(self.hash_functions):
column = hash_function(abs(hash(key)))
value = min(self.count[row, column], value)
return value
def __generate_hash_function(self):
"""
Returns a hash function from a family of pairwise-independent hash
functions
"""
a, b = random_parameter(), random_parameter()
return lambda x: (a * x + b) % BIG_PRIME % self.w
In [ ]:
# define a function to return a list of the exact top users, sorted by count
def exact_top_users(f, top_n = 10):
import operator
counts = {}
for user in f:
user = user.rstrip('\n')
try:
if user not in counts:
counts[user] = 1
else:
counts[user] += 1
except ValueError:
pass
except KeyError:
pass
counter = 0
results = []
for user,count in reversed(sorted(counts.iteritems(), key=operator.itemgetter(1))):
if counter >= top_n:
break
results.append('{},{}'.format(user,str(count)))
counter += 1
return results
# note that the output format is '[user] [count]'
In [ ]:
f = open('CM_small.txt')
results_exact = sorted(exact_top_users(f))
print(results_exact)
In [ ]:
# define a function to return a list of the estimated top users, sorted by count
def CM_top_users(f, s, top_n = 10):
for user_name in f:
s.update(user_name.rstrip('\n'),1)
results = []
counter = 0
for value in reversed(sorted(s.top_k.values())):
if counter >= top_n:
break
results.append('{1},{0}'.format(str(value[0]),str(value[1])))
counter += 1
return results
# note that the output format is '[user] [count]'
In [ ]:
# instantiate a Sketch object
s = Sketch(10**-3, 0.1, 10)
In [ ]:
f = open('CM_small.txt')
results_CM = sorted(CM_top_users(f,s))
print(results_CM)
In [ ]:
for item in zip(results_exact,results_CM):
print(item)
Is it possible to make the sketch so coarse that its estimates are wrong even for this data set?
In [ ]:
s = Sketch(0.9, 0.9, 10)
f = open('CM_small.txt')
results_coarse_CM = CM_top_users(f,s)
print(results_coarse_CM)
Yes! (if you try enough) Why?
So, you're dealing with a space with minimum size 3 x 1. With 10 records, it's possible that all 4 users map their counts to the point. So it's possible to see an estimate as high as 10, in this case.
In [ ]:
f = open('CM_large.txt')
%time results_exact = exact_top_users(f)
print(results_exact)
In [ ]:
# this could take a few minutes
f = open('CM_large.txt')
s = Sketch(10**-4, 0.001, 10)
%time results_CM = CM_top_users(f,s)
print(results_CM)
For this precision and dataset size, the CM algo takes much longer than the exact solution. In fact, the crossover point at which the CM sketch can achieve reasonable accuracy in the same time as the exact solution is a very large number of entries.
In [ ]:
for item in zip(results_exact,results_CM):
print(item)
In [ ]:
# the CM sketch gets the top entry (an outlier) correct but doesn't do well estimating the order of the more degenerate counts
# let's decrease the precision via both the epsilon and delta parameters, and see whether it still gets the "heavy-hitter" correct
f = open('CM_large.txt')
s = Sketch(10**-3, 0.01, 10)
%time results_CM = CM_top_users(f,s)
print(results_CM)
In [ ]:
# nope...sketch is too coarse, too many collisions, and the prominence of user 'Euph0r1a__ 129' is obscured
for item in zip(results_exact,results_CM):
print(item)
The most common use of the CM sketch is analysis of streaming data. Why?
Take away: use the CM sketch to estimate of the top-k most frequent elements in a streaming environment.
In [ ]: