org.wso2.extension.siddhi.execution.approximate.count

Class CountMinSketch<E>

java.lang.Object

org.wso2.extension.siddhi.execution.approximate.count.CountMinSketch<E>

Type Parameters:

E - is the type of data to be counted

All Implemented Interfaces:

Serializable

public class CountMinSketch<E>
extends Object
implements Serializable

A probabilistic data structure to keep count of different items. The referred research paper - Count-Min Sketch by Graham Cormode http://dimacs.rutgers.edu/%7Egraham/pubs/papers/cmencyc.pdf

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
CountMinSketch(double relativeError, double confidence) Instantiate the count min sketch based on a given relative error and confidence

Method Summary

Modifier and Type	Method and Description
void	clear() Clears the counts within the sketch.
long[]	getConfidenceInterval(long count) Calculate the confidence interval of the approximate count [approximateCount - (totalNoOfItems * relativeError), approximateCount + (totalNoOfItems * relativeError)]
long	insert(E item) Adds the count of an item to the count min sketch calculate hash values relevant for each row in the count array compute indices in the range of [0, width) from those hash values increment each value in the cell of relevant row and index (e.g.
long	remove(E item) Removes the count of an item from the count min sketch calculate hash values relevant for each row in the count array compute indices in the range of [0, width) from those hash values decrement each value in the cell of relevant row and index (e.g.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

CountMinSketch

public CountMinSketch(double relativeError,
                      double confidence)

Instantiate the count min sketch based on a given relative error and confidence

Parameters:

relativeError - is a positive number less than 1 (e.g. 0.01)

confidence - is a positive number less than 1 (e.g. 0.01) which is the probability of answers being within the relative error

Method Detail

insert

public long insert(E item)

Adds the count of an item to the count min sketch calculate hash values relevant for each row in the count array compute indices in the range of [0, width) from those hash values increment each value in the cell of relevant row and index (e.g. countArray[row][index]++)

Parameters:

item - is the item to be inserted

Returns:

the approximate count of the item

remove

public long remove(E item)

Removes the count of an item from the count min sketch calculate hash values relevant for each row in the count array compute indices in the range of [0, width) from those hash values decrement each value in the cell of relevant row and index (e.g. countArray[row][index]--)

Parameters:

item - is the item to be inserted

Returns:

the approximate count of the item

getConfidenceInterval

public long[] getConfidenceInterval(long count)

Calculate the confidence interval of the approximate count [approximateCount - (totalNoOfItems * relativeError), approximateCount + (totalNoOfItems * relativeError)]

Parameters:

count - is the approximate count

Returns:

a long array which contains the lower bound and the upper bound of the confidence interval consecutively

clear

public void clear()

Clears the counts within the sketch.