public class HyperLogLog3Linear64
extends Object
Cardinality estimation with the HyperLogLog algorithm, using the tail cut
mechanism. Tail cut is described in the paper "Better with Fewer Bits -
Improving the Performance of Cardinality Estimation of Large Data Streams"
from Qingjun Xiao, You Zhou, Shigang Chen, in
http://cse.seu.edu.cn/PersonalPage/csqjxiao/csqjxiao_files/papers/INFOCOM17.pdf
It uses linear counting for 60 bits, until 36 bits are set, then switches to
HyperLogLog. There, it uses 20 counters of 3 bits each (re-using the linear
counting data), and 4 bits for a base counter, which is increased if all
counters are larger than zero.
It is a little bit "order-dependent", that is, adding the same entry multiple
times can change the internal state. However, unlike in HyperBitBit, here the
effect is very small.