org.wso2.extension.siddhi.execution.approximate.distinctcount

Class HyperLogLog<E>

java.lang.Object

org.wso2.extension.siddhi.execution.approximate.distinctcount.HyperLogLog<E>

Type Parameters:

E - is the type of objects in the set.

All Implemented Interfaces:

Serializable

public class HyperLogLog<E>
extends Object
implements Serializable

A probabilistic data structure to calculate the distinctCount of a set. The referred research paper - HyperLogLog: the analysis of a near-optimal distinctCount estimation algorithm by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier. http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
HyperLogLog(double relativeError, double confidence, boolean pastCountsEnabled) Create a new HyperLogLog by specifying the relative error and confidence of answers being within the error margin.

Method Summary

Modifier and Type	Method and Description
void	addItem(E item) Adds a new item to the array by hashing and increasing the count of relevant buckets
void	clear() Clears all the counts stored in the data structure.
long	getCardinality()
long[]	getConfidenceInterval() Calculate the confidence interval for the current distinctCount.
int	getHashValue(Object value) Compute an integer hash value for a given value
void	removeItem(E item) Removes the given item from the array and restore the distinctCount value by using the previous count.

Methods inherited from class java.lang.Object

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

Constructor Detail

HyperLogLog

public HyperLogLog(double relativeError,
                   double confidence,
                   boolean pastCountsEnabled)

Create a new HyperLogLog by specifying the relative error and confidence of answers being within the error margin. Based on the relative error the array size is calculated.

Parameters:

relativeError - is a number in the range (0, 1)

confidence - is a value out of 0.65, 0.95, 0.99

pastCountsEnabled - is a boolean value to mention whether to keep track of past counts or not.

Method Detail

getCardinality

public long getCardinality()

Returns:

the current distinctCount value

getConfidenceInterval

public long[] getConfidenceInterval()

Calculate the confidence interval for the current distinctCount. The confidence values can be one value out of 0.65, 0.95, 0.99.

Returns:

an long array which contain the lower bound and the upper bound of the confidence interval e.g. - {310, 350} for the distinctCount of 330

addItem

public void addItem(E item)

Adds a new item to the array by hashing and increasing the count of relevant buckets

Parameters:

item - is the item to be inserted

removeItem

public void removeItem(E item)

Removes the given item from the array and restore the distinctCount value by using the previous count.

Parameters:

item - is the item to be removed

getHashValue

public int getHashValue(Object value)

Compute an integer hash value for a given value

Parameters:

value - to be hashed

Returns:

integer hash value

clear

public void clear()

Clears all the counts stored in the data structure.