Package cn.net.pap.common.datastructure.frequency

Class CountMinSketch

java.lang.Object

cn.net.pap.common.datastructure.frequency.CountMinSketch

All Implemented Interfaces:

Serializable

public class CountMinSketch
extends Object
implements Serializable

Count-Min Sketch datastructure. An Improved Data Stream Summary: The Count-Min Sketch and its Applications https://web.archive.org/web/20060907232042/http://www.eecs.harvard.edu/~michaelm/CS222/countmin.pdf

See Also:

• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	CountMinSketch.CMSMergeException

Field Summary

Fields

Modifier and Type	Field	Description
static final long	PRIME_MODULUS

Constructor Summary

Constructors

Constructor	Description
CountMinSketch(double epsOfTotalCount, double confidence, int seed)
CountMinSketch(int depth, int width, int seed)

Method Summary

Modifier and Type	Method	Description
void	add(long item, long count)
void	add(String item, long count)
static CountMinSketch	deserialize(byte[] data)
boolean	equals(Object o)
long	estimateCount(long item)	The estimate is correct within 'epsilon' * (total item count), with probability 'confidence'.
long	estimateCount(String item)
double	getConfidence()
static int[]	getHashBuckets(String key, int hashCount, int max)
double	getRelativeError()
int	hashCode()
static CountMinSketch	merge(CountMinSketch... estimators)	Merges count min sketches to produce a count min sketch for their combined streams
static byte[]	serialize(CountMinSketch sketch)
long	size()
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Details

PRIME_MODULUS

public static final long PRIME_MODULUS

See Also:

• Constant Field Values

Constructor Details

CountMinSketch

public CountMinSketch(int depth,
 int width,
 int seed)

CountMinSketch

public CountMinSketch(double epsOfTotalCount,
 double confidence,
 int seed)

Method Details

toString

public String toString()

Overrides:

toString in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

getRelativeError

public double getRelativeError()

getConfidence

public double getConfidence()

add

public void add(long item,
 long count)

add

public void add(String item,
 long count)

size

public long size()

estimateCount

public long estimateCount(long item)

The estimate is correct within 'epsilon' * (total item count), with probability 'confidence'.

estimateCount

public long estimateCount(String item)

merge

public static CountMinSketch merge(CountMinSketch... estimators)
                            throws CountMinSketch.CMSMergeException

Merges count min sketches to produce a count min sketch for their combined streams

Parameters:

estimators -

Returns:

merged estimator or null if no estimators were provided

Throws:

CountMinSketch.CMSMergeException - if estimators are not mergeable (same depth, width and seed)

serialize

public static byte[] serialize(CountMinSketch sketch)

deserialize

public static CountMinSketch deserialize(byte[] data)

getHashBuckets

public static int[] getHashBuckets(String key,
 int hashCount,
 int max)