org.apache.hadoop.hbase.util

Class LossyCounting<T>

java.lang.Object

org.apache.hadoop.hbase.util.LossyCounting<T>

@InterfaceAudience.Private
public class LossyCounting<T>
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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	LossyCounting.LossyCountingListener<T>
(package private) class	LossyCounting.SweepRunnable

Field Summary

Fields

Modifier and Type	Field and Description
private long	bucketSize
private int	currentTerm
private Map<T,Integer>	data
private ExecutorService	executor
private static AtomicReference<Future<?>>	fut
private LossyCounting.LossyCountingListener<T>	listener
private static org.slf4j.Logger	LOG
private String	name
private long	totalDataCount

Constructor Summary

Constructors

Constructor and Description
LossyCounting(String name, org.apache.hadoop.conf.Configuration conf)
LossyCounting(String name, org.apache.hadoop.conf.Configuration conf, LossyCounting.LossyCountingListener<T> listener)
LossyCounting(String name, double errorRate)
LossyCounting(String name, double errorRate, LossyCounting.LossyCountingListener<T> listener)

Method Summary

Modifier and Type	Method and Description
void	add(T key)
private void	addByOne(T key)
private void	calculateCurrentTerm() Calculate and set current term
boolean	contains(T key)
long	getBucketSize()
long	getCurrentTerm()
long	getDataSize()
Set<T>	getElements()
Future<?>	getSweepFuture()
void	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

executor

private final ExecutorService executor

bucketSize

private long bucketSize

currentTerm

private int currentTerm

data

private Map<T,Integer> data

totalDataCount

private long totalDataCount

name

private final String name

listener

private LossyCounting.LossyCountingListener<T> listener

fut

private static AtomicReference<Future<?>> fut

Constructor Detail

LossyCounting

LossyCounting(String name,
              double errorRate)

LossyCounting

public LossyCounting(String name,
                     double errorRate,
                     LossyCounting.LossyCountingListener<T> listener)

LossyCounting

LossyCounting(String name,
              org.apache.hadoop.conf.Configuration conf)

LossyCounting

public LossyCounting(String name,
                     org.apache.hadoop.conf.Configuration conf,
                     LossyCounting.LossyCountingListener<T> listener)

Method Detail

addByOne

private void addByOne(T key)

add

public void add(T key)

sweep

public void sweep()

sweep low frequency data

calculateCurrentTerm

private void calculateCurrentTerm()

Calculate and set current term

getBucketSize

public long getBucketSize()

getDataSize

public long getDataSize()

contains

public boolean contains(T key)

getElements

public Set<T> getElements()

getCurrentTerm

public long getCurrentTerm()

getSweepFuture

public Future<?> getSweepFuture()