For more information see the following references:
- Count-Min sketch: https://sites.google.com/site/countminsketch/
- next big thing syndrome: http://lkozma.net/blog/sketching-data-structures/
- G. Cormode, S. Muthukrishnan. "Approximating Data with the Count-Min Data Structure". IEEE Trans. on Software (2012)
//Import libraryvar createCountMinSketch =//Create data structurevar sketch =//Increment counterssketchsketch//Query resultsconsole //Prints 104console //Prints 1
npm install count-min-sketch
module.exports is a constructor for the data structure, and you import it like so:
var createCountMinSketch =
var sketch = createCountMinSketch(epsilon, probError[, hashFunc])
Creates a count-min sketch data structure.
epsilonis the accuracy of the data structure (ie the size of bins that we are computing frequencies of)
probErroris the probability of incorrectly computing a value
hashFunc(key, hashes)is a hash function for the data structure. (optional) the parameters to this function are as follows:
keyis the item that is being hashed
hashesis an array of
khashes which are required to be pairwise independent.
Returns A count-min sketch data structure
keyis the item in the table to increment.
vis the amount to add to it
Returns the frequency of the item
keyis the item whose frequency we are counting
Returns An estimate of the frequency of
Returns a serializable JSON representation of the table.
Converts a JSON object into a deserialized sketch. The hash function is reused from the current sketch.
Note In order for this to be successful both the serialized hash table and the current hash table have to have the same hash function.
(c) 2013 Mikola Lysenko. MIT License