org.apache.hadoop.hive.common.ndv.hll

Class HyperLogLogUtils

java.lang.Object

org.apache.hadoop.hive.common.ndv.hll.HyperLogLogUtils

public class HyperLogLogUtils
extends Object

HyperLogLog serialization utilities.

Field Summary

Fields

Modifier and Type	Field and Description
static byte[]	MAGIC

Constructor Summary

Constructors

Constructor and Description
HyperLogLogUtils()

Method Summary

Modifier and Type	Method and Description
static HyperLogLog	deserializeHLL(byte[] buf) This function deserializes the serialized hyperloglogs from a byte array.
static HyperLogLog	deserializeHLL(InputStream in) Refer serializeHLL() for format of serialization.
static long	getEstimatedCountFromSerializedHLL(InputStream in) Get estimated cardinality without deserializing HLL
static float	getRelativeError(long actualCount, long estimatedCount) Return relative error between actual and estimated cardinality
static void	serializeHLL(OutputStream out, HyperLogLog hll) HyperLogLog is serialized using the following format

Methods inherited from class java.lang.Object

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

Field Detail

MAGIC

public static final byte[] MAGIC

Constructor Detail

HyperLogLogUtils

public HyperLogLogUtils()

Method Detail

serializeHLL

public static void serializeHLL(OutputStream out,
                                HyperLogLog hll)
                         throws IOException

HyperLogLog is serialized using the following format

 |-4 byte-|------varlong----|varint (optional)|----------|  
 ---------------------------------------------------------
 | header | estimated-count | register-length | register |
 ---------------------------------------------------------
 
 4 byte header is encoded like below
 3 bytes - HLL magic string to identify serialized stream
 4 bits  - p (number of bits to be used as register index)
 1       - spare bit (not used)
 3 bits  - encoding (000 - sparse, 001..110 - n bit packing, 111 - no bit packing)
 
 Followed by header are 3 fields that are required for reconstruction
 of hyperloglog
 Estimated count - variable length long to store last computed estimated count.
                   This is just for quick lookup without deserializing registers
 Register length - number of entries in the register (required only for 
                   for sparse representation. For bit-packing, the register
                   length can be found from p)
 

Parameters:

out - - output stream to write to

hll - - hyperloglog that needs to be serialized

Throws:

IOException

deserializeHLL

public static HyperLogLog deserializeHLL(InputStream in)
                                  throws IOException

Refer serializeHLL() for format of serialization. This function deserializes the serialized hyperloglogs

Parameters:

in - - input stream

Returns:

deserialized hyperloglog

Throws:

IOException

deserializeHLL

public static HyperLogLog deserializeHLL(byte[] buf)

This function deserializes the serialized hyperloglogs from a byte array.

Parameters:

buf - - to deserialize

Returns:

HyperLogLog

getEstimatedCountFromSerializedHLL

public static long getEstimatedCountFromSerializedHLL(InputStream in)
                                               throws IOException

Get estimated cardinality without deserializing HLL

Parameters:

in - - serialized HLL

Returns:

- cardinality

Throws:

IOException

getRelativeError

public static float getRelativeError(long actualCount,
                                     long estimatedCount)

Return relative error between actual and estimated cardinality

Parameters:

actualCount - - actual count

estimatedCount - - estimated count

Returns:

relative error