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

Class HLLSparseRegister

java.lang.Object

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

All Implemented Interfaces:

HLLRegister

public class HLLSparseRegister
extends Object
implements HLLRegister

Constructor Summary

Constructors

Constructor and Description
HLLSparseRegister(int p, int pp, int qp)

Method Summary

Modifier and Type	Method and Description
boolean	add(long hashcode) Specify a hashcode to add to hyperloglog register.
int	encodeHash(long hashcode) Input: 64 bit hashcode |---------w-------------| |------------p'----------| 10101101.......1010101010 10101010101 01010101010101 |------p-----| Output: 32 bit int |b| |-q'-| |------------p'----------| 1 010101 01010101010 10101010101010 |------p-----| The default values of p', q' and b are 25, 6, 1 (total 32 bits) respectively.
boolean	equals(Object obj)
void	extractLowBitsTo(HLLRegister dest)
int	getP()
int	getPPrime()
int	getSize()
TreeMap<Integer,Byte>	getSparseMap()
int	hashCode()
void	merge(HLLRegister hllRegister) Merge hyperloglog registers of the same type (SPARSE or DENSE register)
boolean	set(int key, byte value) Instead of specifying hashcode, this interface can be used to directly specify the register index and register value.
String	toExtendedString()
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

HLLSparseRegister

public HLLSparseRegister(int p,
                         int pp,
                         int qp)

Method Detail

add

public boolean add(long hashcode)

Description copied from interface: HLLRegister

Specify a hashcode to add to hyperloglog register.

Specified by:

add in interface HLLRegister

Parameters:

hashcode - - hashcode to add

Returns:

true if register value is updated else false

encodeHash

public int encodeHash(long hashcode)

 Input: 64 bit hashcode
 
 |---------w-------------| |------------p'----------|
 10101101.......1010101010 10101010101 01010101010101
                                       |------p-----|
                                       
 Output: 32 bit int
 
 |b| |-q'-|  |------------p'----------|
  1  010101  01010101010 10101010101010
                         |------p-----|
                    
 
 The default values of p', q' and b are 25, 6, 1 (total 32 bits) respectively.
 This function will return an int encoded in the following format
 
 p  - LSB p bits represent the register index
 p' - LSB p' bits are used for increased accuracy in estimation
 q' - q' bits after p' are left as such from the hashcode if b = 0 else
      q' bits encodes the longest trailing zero runs from in (w-p) input bits
 b  - 0 if longest trailing zero run is contained within (p'-p) bits
      1 if longest trailing zero run is computeed from (w-p) input bits and
      its value is stored in q' bits
 

Parameters:

hashcode -

Returns:

getSize

public int getSize()

merge

public void merge(HLLRegister hllRegister)

Description copied from interface: HLLRegister

Merge hyperloglog registers of the same type (SPARSE or DENSE register)

Specified by:

merge in interface HLLRegister

Parameters:

hllRegister - - register to be merged

set

public boolean set(int key,
                   byte value)

Description copied from interface: HLLRegister

Instead of specifying hashcode, this interface can be used to directly specify the register index and register value. This interface is useful when reconstructing hyperloglog from a serialized representation where its not possible to regenerate the hashcode.

Specified by:

set in interface HLLRegister

Parameters:

key - - register index

value - - register value

Returns:

true if register value is updated else false

getSparseMap

public TreeMap<Integer,Byte> getSparseMap()

extractLowBitsTo

public void extractLowBitsTo(HLLRegister dest)

getP

public int getP()

getPPrime

public int getPPrime()

toString

public String toString()

Overrides:

toString in class Object

toExtendedString

public String toExtendedString()

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object