io.druid.query.aggregation.hyperloglog

Class HyperLogLogCollector

java.lang.Object

io.druid.query.aggregation.hyperloglog.HyperLogLogCollector

All Implemented Interfaces:

Comparable<HyperLogLogCollector>

Direct Known Subclasses:

HLLCV0, HLLCV1

public abstract class HyperLogLogCollector
extends Object
implements Comparable<HyperLogLogCollector>

Implements the HyperLogLog cardinality estimator described in: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf Run this code to see a simple indication of expected errors based on different m values: for (int i = 1; i < 20; ++i) { System.out.printf("i[%,d], val[%,d] => error[%f%%]%n", i, 2 << i, 104 / Math.sqrt(2 << i)); } This class is *not* multi-threaded. It can be passed among threads, but it is written with the assumption that only one thread is ever calling methods on it. If you have multiple threads calling methods on this concurrently, I hope you manage to get correct behavior

Field Summary

Fields

Modifier and Type	Field and Description
static int	BITS_FOR_BUCKETS
static double	CORRECTION_PARAMETER
static int	DENSE_THRESHOLD
static double	HIGH_CORRECTION_THRESHOLD
static double	LOW_CORRECTION_THRESHOLD
static int	NUM_BUCKETS
static int	NUM_BYTES_FOR_BUCKETS

Constructor Summary

Constructors

Constructor and Description
HyperLogLogCollector(ByteBuffer byteBuffer)

Method Summary

Methods

Modifier and Type	Method and Description
void	add(byte[] hashedValue)
void	add(short bucket, byte positionOf1)
static double	applyCorrection(double e, int zeroCount)
int	compareTo(HyperLogLogCollector other)
boolean	equals(Object o)
double	estimateByteBuffer(ByteBuffer buf)
double	estimateCardinality()
HyperLogLogCollector	fold(ByteBuffer buffer)
HyperLogLogCollector	fold(HyperLogLogCollector other)
protected int	getInitPosition()
static int	getLatestNumBytesForDenseStorage()
abstract short	getMaxOverflowRegister()
abstract byte	getMaxOverflowValue()
abstract int	getNumBytesForDenseStorage()
abstract int	getNumHeaderBytes()
abstract short	getNumNonZeroRegisters()
abstract int	getPayloadBytePosition()
abstract int	getPayloadBytePosition(ByteBuffer buffer)
abstract byte	getRegisterOffset()
protected ByteBuffer	getStorageBuffer()
abstract byte	getVersion()
int	hashCode()
static HyperLogLogCollector	makeCollector(ByteBuffer buffer)
static byte[]	makeEmptyVersionedByteArray()
static HyperLogLogCollector	makeLatestCollector()
abstract void	setMaxOverflowRegister(ByteBuffer buffer, short register)
abstract void	setMaxOverflowRegister(short register)
abstract void	setMaxOverflowValue(byte value)
abstract void	setMaxOverflowValue(ByteBuffer buffer, byte value)
abstract void	setNumNonZeroRegisters(ByteBuffer buffer, short numNonZeroRegisters)
abstract void	setNumNonZeroRegisters(short numNonZeroRegisters)
abstract void	setRegisterOffset(byte registerOffset)
abstract void	setRegisterOffset(ByteBuffer buffer, byte registerOffset)
abstract void	setVersion(ByteBuffer buffer)
byte[]	toByteArray()
ByteBuffer	toByteBuffer()
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

DENSE_THRESHOLD

public static final int DENSE_THRESHOLD

See Also:

Constant Field Values

BITS_FOR_BUCKETS

public static final int BITS_FOR_BUCKETS

See Also:

Constant Field Values

NUM_BUCKETS

public static final int NUM_BUCKETS

See Also:

Constant Field Values

NUM_BYTES_FOR_BUCKETS

public static final int NUM_BYTES_FOR_BUCKETS

See Also:

Constant Field Values

LOW_CORRECTION_THRESHOLD

public static final double LOW_CORRECTION_THRESHOLD

See Also:

Constant Field Values

HIGH_CORRECTION_THRESHOLD

public static final double HIGH_CORRECTION_THRESHOLD

CORRECTION_PARAMETER

public static final double CORRECTION_PARAMETER

See Also:

Constant Field Values

Constructor Detail

HyperLogLogCollector

public HyperLogLogCollector(ByteBuffer byteBuffer)

Method Detail

makeLatestCollector

public static HyperLogLogCollector makeLatestCollector()

makeCollector

public static HyperLogLogCollector makeCollector(ByteBuffer buffer)

getLatestNumBytesForDenseStorage

public static int getLatestNumBytesForDenseStorage()

makeEmptyVersionedByteArray

public static byte[] makeEmptyVersionedByteArray()

applyCorrection

public static double applyCorrection(double e,
                     int zeroCount)

getVersion

public abstract byte getVersion()

setVersion

public abstract void setVersion(ByteBuffer buffer)

getRegisterOffset

public abstract byte getRegisterOffset()

setRegisterOffset

public abstract void setRegisterOffset(byte registerOffset)

setRegisterOffset

public abstract void setRegisterOffset(ByteBuffer buffer,
                     byte registerOffset)

getNumNonZeroRegisters

public abstract short getNumNonZeroRegisters()

setNumNonZeroRegisters

public abstract void setNumNonZeroRegisters(short numNonZeroRegisters)

setNumNonZeroRegisters

public abstract void setNumNonZeroRegisters(ByteBuffer buffer,
                          short numNonZeroRegisters)

getMaxOverflowValue

public abstract byte getMaxOverflowValue()

setMaxOverflowValue

public abstract void setMaxOverflowValue(byte value)

setMaxOverflowValue

public abstract void setMaxOverflowValue(ByteBuffer buffer,
                       byte value)

getMaxOverflowRegister

public abstract short getMaxOverflowRegister()

setMaxOverflowRegister

public abstract void setMaxOverflowRegister(short register)

setMaxOverflowRegister

public abstract void setMaxOverflowRegister(ByteBuffer buffer,
                          short register)

getNumHeaderBytes

public abstract int getNumHeaderBytes()

getNumBytesForDenseStorage

public abstract int getNumBytesForDenseStorage()

getPayloadBytePosition

public abstract int getPayloadBytePosition()

getPayloadBytePosition

public abstract int getPayloadBytePosition(ByteBuffer buffer)

getInitPosition

protected int getInitPosition()

getStorageBuffer

protected ByteBuffer getStorageBuffer()

add

public void add(byte[] hashedValue)

add

public void add(short bucket,
       byte positionOf1)

fold

public HyperLogLogCollector fold(HyperLogLogCollector other)

fold

public HyperLogLogCollector fold(ByteBuffer buffer)

toByteBuffer

public ByteBuffer toByteBuffer()

toByteArray

public byte[] toByteArray()

estimateCardinality

public double estimateCardinality()

estimateByteBuffer

public double estimateByteBuffer(ByteBuffer buf)

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

toString

public String toString()

Overrides:

toString in class Object

compareTo

public int compareTo(HyperLogLogCollector other)

Specified by:

compareTo in interface Comparable<HyperLogLogCollector>