of underestimating the cardinalities, they are now overestimated. Another indication for
the incorrectness of the proposed large range correction is the fact that it is not even
defined for all possible states. For instance, consider a (p, q)-HyperLogLog sketch with
p+q = 32 for which all registers are equal to the maximum possible value q +1. The raw
estimate would be ˆn
raw
= α
m
2
33
, which is greater than 2
32
and outside of the domain
of the large range correction formula.
A simple approach to avoid the need of any large range correction is to extend the
operating range of the raw estimator to larger cardinalities. This can be easily accom-
plished by increasing p + q, which corresponds to using hash values with more bits.
Each additional bit doubles the operating range which scales like 2
p+q
. However, in case
q ≥ 31 the number of possible register values, which are {0, 1, . . . , q + 1}, is greater than
32 which is no longer representable by 5-bit registers. Therefore, it was proposed to use
6 bits per register in combination with 64-bit hash values [7]. Even larger hash values
are needless in practice, because it is unrealistic to encounter cardinalities of order 2
64
.
3.1. Derivation of the raw estimator
In order to better understand why the raw estimator fails for small and large cardinalities,
we start with a brief and simple derivation without the restriction to large cardinalities
(n → ∞) and without using complex analysis as in [6].
Let us assume that the register values have following cumulative distribution function
P (K ≤ k|λ) = e
−
λ
m2
k
. (16)
For now we ignore that this distribution has infinite support and differs from the register
value distribution under the Poisson model (6), whose support is limited to the range
[0, q + 1]. For a random variable K obeying (16) the expectation of 2
−K
is given by
E(2
−K
) =
∞
X
k=−∞
2
−k
e
−
λ
m2
k
− e
−
λ
m2
k−1
=
1
2
∞
X
k=−∞
2
k
e
−
λ
m
2
k
=
α
∞
m ξ(log
2
(λ/m))
λ
, (17)
where the function
ξ(x) := log(2)
∞
X
k=−∞
2
k+x
e
−2
k+x
(18)
is a smooth periodic function with period 1. Numerical evaluations indicate that this
function can be bounded by 1 −ε
ξ
≤ ξ(x) ≤ 1 + ε
ξ
with ε
ξ
:= 9.885 × 10
−6
(see Fig. 4).
This value can also be found using Fourier analysis as shown in Appendix A.
Let K
1
, . . . , K
m
be a sample distributed according to (16). For large sample sizes
m → ∞ we have asymptotically
E
1
2
−K
1
+ . . . + 2
−K
m
=
m→∞
1
E(2
−K
1
+ . . . + 2
−K
m
)
=
1
mE(2
−K
)
. (19)
11
我的内容管理
展开
