org.apache.hadoop.hbase.util

Class LossyCounting

java.lang.Object

org.apache.hadoop.hbase.util.LossyCounting

@InterfaceAudience.Public
public class LossyCounting
extends Object

LossyCounting utility, bounded data structure that maintains approximate high frequency elements in data stream. Bucket size is 1 / error rate. (Error rate is 0.02 by default) Lemma If element
does not appear in set, then is frequency is less than e * N (N is total element counts until now.) Based on paper: http://www.vldb.org/conf/2002/S10P03.pdf

Field Summary

Fields

Modifier and Type	Field and Description
private long	bucketSize
private long	currentTerm
private Map<String,Integer>	data
private double	errorRate
private static org.slf4j.Logger	LOG
private long	totalDataCount

Constructor Summary

Constructors

Constructor and Description
LossyCounting()
LossyCounting(double errorRate)

Method Summary

Modifier and Type	Method and Description
Set<String>	addByOne(String key)
private void	calculateCurrentTerm() Calculate and set current term
boolean	contains(String key)
long	getBuketSize()
long	getCurrentTerm()
long	getDataSize()
private Set<String>	sweep() sweep low frequency data

Methods inherited from class java.lang.Object

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

Field Detail

LOG

private static final org.slf4j.Logger LOG

bucketSize

private long bucketSize

currentTerm

private long currentTerm

errorRate

private double errorRate

data

private Map<String,Integer> data

totalDataCount

private long totalDataCount

Constructor Detail

LossyCounting

public LossyCounting(double errorRate)

LossyCounting

public LossyCounting()

Method Detail

addByOne

public Set<String> addByOne(String key)

sweep

private Set<String> sweep()

sweep low frequency data

Returns:

Names of elements got swept

calculateCurrentTerm

private void calculateCurrentTerm()

Calculate and set current term

getBuketSize

public long getBuketSize()

getDataSize

public long getDataSize()

contains

public boolean contains(String key)

getCurrentTerm

public long getCurrentTerm()