Approximating Streaming Data with Sketching - Real-Time Analytics - page 438

int m;
public HyperLogLog(int b) throws IOException {
output = new ObjectOutputStream(hash);
this.b = b;
if(b < 4) b = 4; else if(b > 16) b = 16;
m = 1 << b;
M = new byte[m];
for(int i=0;i<m;i++) M[i] = 0;
V = M.length;
switch(b) {
case 4: alpha = 0.673*m*m;break;
case 5: alpha = 0.697*m*m;break;
case 6: alpha = 0.709*m*m;break;
default: alpha = (0.7212/(1+1.079/m))*m*m;
}
}
Note that some of the constants used in the cardinality computation are
precomputed here to save later processing.
Next comes the add(E arg0) method. Because it is expected that the
size of the set will be requested frequently, this implementation maintains
the sum of registers directly. This removes the O(m) computation from the
cardinality estimate. For the same reason it also maintains the count of
empty registers for use with the small cardinality correction. This gives a
slightly more complicated implementation and Min-Count:
public boolean add(E e) {
try {
hash.reset();
output.writeObject(e);
int x = hash.hash();
int j = x >>> (Integer. MAX_VALUE - b);
x = (x << b)|(1 << (b-1)) + 1;
int r = Integer. numberOfLeadingZeros (x)+1;
if(M[j] == 0) {
V--;
M[j] = (byte)r;
return true;