HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm
Discrete Mathematics & Theoretical Computer Science, 2007 · paper · Computer science
Describes and analyses HyperLogLog, a probabilistic algorithm that estimates the number of distinct elements in very large data streams in one pass. With m memory units its standard error is about 1.04/√m, matching LogLog's accuracy with 64% of the memory.
Checked: PDF from dmtcs.episciences.org, fetched 4 Oct 2026. Page numbers are those of that PDF.
5 findings
Substance "J0(4) = 1/L^4 (4/15 π^4 − π^2L^2 − 3L^4 − 21Lζ(3) − 24 Li4(1/2))": the π^2L^2 term should be +. As printed the bracket is ≈ −9.38, which is impossible for J0(4) = ∫ f(u)^4 du > 0.
- p. 13 Section 3.2, closed form of J0(4)
4/15 π4 − π2L2 − 3L4 − 21Lζ(3) − 24 Li4(1/2)
- p. 13 Section 3.2, closed form for J0(4)
J0(4) = 1/L4 ( 4/15 π4 − π2L2 − 3L4 − 21Lζ(3) − 24 Li4(1/2) )
Only the authors can say what is right here.
Judge's note: The p.13 image shows '− π^2L^2'. I worked it independently. Substituting w = 1/(1+u) gives J0(m) = L^{-m} ∫_0^1 log^m(1+w)/w^2 dw. This reproduces the paper's J0(2) = π^2/(6L^2) − 2 exactly. For m=4, integration by parts gives −2L^4 + 4 I3, with I3 = ∫_0^1 log^3(1+w)/w dw = π^4/15 + π^2L^2/4 − L^4/4 − (21/4)Lζ(3) − 6Li4(1/2) ≈ 0.1425. A Simpson check with h = 0.25 gives ≈ 0.1427. So L^4 J0(4) = (4/15)π^4 + π^2L^2 − 3L^4 − 21Lζ(3) − 24Li4(1/2) ≈ 0.108, and J0(4) ≈ 0.469. The closed form is a stated formula that is wrong as printed.
Second check: another model agreed
Report a problem with this finding
Substance In Fig. 3, the corrections are three independent statements ('if E ≤ 5/2 m then ...', 'if E ≤ 1/30 2^32 then set E* := E', 'if E > 1/30 2^32 then ...'), so the second always overwrites the small-range correction, contrary to "This correction is incorporated in the program of Figure 3."
- p. 14 Fig. 3, correction steps
if E ≤ 1/30 2^32 then set E⋆ := E;
- p. 15 Section 4 (ii), end of small range corrections
This correction is incorporated in the program of Figure 3.
Judge's note: The p.14 image shows three 'if' statements at the same indentation, with no 'else' between them. Any E ≤ (5/2)m ≤ 163840 (m ≤ 2^16) also satisfies E ≤ 2^32/30 ≈ 1.43e8. Read literally, E* is therefore reset to E and the linear-counting correction m log(m/V) is never returned. The intended structure is evidently an if / else-if chain.
Second check: another model agreed
Report a problem with this finding
Substance "are expected to be within σ, 2σ, 3σ of the exact count in respectively 65%, 95%, 99% of all the cases": under the stated Gaussian approximation, ±1σ coverage is about 68%, not 65%.
- p. 15 Section 4, boxed statement on accuracy
within σ, 2σ, 3σ of the exact count in respectively 65%, 95%, 99% of all the cases
- p. 15 Section 4, displayed italic statement after 'Accordingly:'
are expected to be within σ, 2σ, 3σ of the exact count in respectively 65%, 95%, 99% of all the cases
- p. 15 Section 4, Gaussian statement
respectively 65%, 95%, 99%
Judge's note: The p.15 image confirms the text. The paper explicitly bases the figures on approximate Gaussianity (the CLT, Fig. 4). Standard normal coverage is 68.3%, 95.4% and 99.7%. The 2σ and 3σ values are rounded down, but 68.3% does not round to 65%.
Second check: another model agreed
Report a problem with this finding
Wording In the proof of Lemma 1, the residues are printed as "Res(h*_u(s)x^{-s},0) = (1/log 2) log((2+u)/(1+u))" and "(1/log 2) x^{-η_k}Γ(η_k)(...)", but with (12) both should carry a minus sign. As printed they conflict with the minus in (13) and the positivity of h_u.
- p. 8 Equation (13) and the residue display below it
Res (h⋆u(s)x−s, 0) = 1/log 2 log((2 + u)/(1 + u))
- p. 8 Equation (13)
hu(x) = −Σ Res(h⋆u(s)x−s, ηk)
- p. 8 Equation (13)
hu(x) = − Σ k∈Z Res(h⋆u(s)x−s, ηk)
- p. 9 Equation (16)
Res(h⋆u(s)x−s, ηk) − log2((2 + u)/(1 + u))
Only the authors can say what is right here.
Judge's note: My own working, from (12) as printed on p.8. Near s=0, 1−2^s = −s log2 + O(s^2), so 2^s/(1−2^s) ~ −1/(s log 2). Γ(s)((1+u)^{-s} − (2+u)^{-s}) → log((2+u)/(1+u)), which is analytic at 0. So the residue is −(1/log2)log((2+u)/(1+u)). At η_k, d/ds(1−2^s) = −2^{η_k} log 2, so the residue of 2^s/(1−2^s) is −1/log2. Formula (13) correctly has −Σ Res, because the contour moves right from Re s = −1/2 to Re s = 1. With the printed positive residues, (13) would give h_u ≈ −log2((2+u)/(1+u)) < 0. But h_u is a sum of positive terms (g(y) = e^{-y} − e^{-2y} > 0). Bound (16) on p.9 treats Σ Res ≈ +log2(...), which matches the printed residues but not (13). Lemma 1 still holds once the signs are fixed, so this is a faulty step and the result stands (S3).
Second check: another model agreed
Report a problem with this finding
Wording Eq. (26) prints "V_P(λ)(Z) = λ^2(∫ u f(u)^m du − (∫ f(u)^m du)^2 + ...)", but (24)–(25) with E_P(λ)(Z) = H(λ/m) ≈ (λ/m)J0 (from (9) and (20)) give a prefactor (λ/m)^2.
- p. 12 Equation (26)
VP(λ)(Z) = λ2
- p. 12 Equation (24)
EP(λ)(Z2) = K( λ/m )
- p. 13 Section 3.2, formula for βm
βm = √m
Only the authors can say what is right here.
Judge's note: Checked on p.12 and p.7. By (24) and (25), E(Z^2) = K(λ/m) = (λ/m)^2(J1 + ...). By (9), E_P(x)(Z) = H(x/m), and by (20), H(x) = x(J0 + ...), so E(Z) ≈ (λ/m)J0. Hence V = (λ/m)^2(J1 − J0^2) + ..., and the printed λ^2 is missing 1/m^2. The β_m formula on p.13 (β_m = √m √(J1/J0^2 − 1)) follows only with the (λ/m)^2 scaling: SE = α_m m^2 (n/m)√(J1−J0^2)/n = √(J1/J0^2 − 1). Taken literally, (26) would give an extra factor m. Theorem 1 stands, so the intermediate formula is faulty but the result holds.
Second check: another model agreed
Report a problem with this finding
12 minor (typos and the like; most checked by the judge only)
Reference or label Running header gives "DMTCS proc. AH, 2007, 137–156", but PDF page 2 is numbered 139 and the last page (PDF p.19) is numbered 156, so the article's own pagination runs 138–156.
- p. 1 Running header, first page
DMTCS proc. AH, 2007, 137–156
- p. 2 Page number
139
Only the authors can say what is right here.
Judge's note: Page images show folio 139 on PDF p.2 and 156 on PDF p.19. That makes PDF p.1 page 138, and 19 pages cover 138–156. The header's 137–156 would need 20 pages. The text runs on from p.1 to p.2 ('far too / large'), so no page is missing. Only the authors or the publisher can say which page range is right.
Second check: another model agreed
Report a problem with this finding
Wording "using m = 2048, hashing on 32 bits, and short bytes of 5 bit length each ... using 1.5kB (kilobyte) of storage" (also "1.5 kilobytes" in the abstract): 2048 five-bit registers take 1280 bytes, about 1.25–1.28 kB.
- p. 3 Introduction, last paragraph before Section 1
using 1.5kB (kilobyte) of storage
- p. 1 Abstract
using a memory of only 1.5 kilobytes
- p. 3 Introduction, final paragraph before Section 1
using m = 2048, hashing on 32 bits, and short bytes of 5 bit length each
Judge's note: Checked on p.3 and in the p.1 abstract. The paper says nothing about overhead or rounding. The figure may be deliberately rounded up, so this is a minor consistency point rather than an outright error.
Second check: another model agreed
Report a problem with this finding
Wording In the proof of Proposition 3 (condition C2), the m-th-power bound reads "|G(z/m,t)|^m ≤ 4^m L |e^{-z} e^{-m^2 t/|z|}| + ...", but applying (X+Y)^m ≤ 2^m X^m + 2^m Y^m to X = 2L|e^{-z/m}|e^{-t/2^L} gives 4^m L^m.
- p. 11 Proof of Prop. 3, bound on |G(z/m,t)|^m
≤ 4mL |e−ze−m2t/|z||
Only the authors can say what is right here.
Judge's note: The p.11 image shows '4^m L' with no exponent on L. My working: 2^m (2L)^m = 4^m L^m. The next display, 'A|e^{-z} z log2|z|^m|', uses the m-th power, which fits L^m and not L. The printed inequality might still hold by accident, because the triangle bound is loose, and I could not build a counterexample. So I record this as a step that does not follow and is inconsistent with the next line. Condition C2 is unaffected.
Second check: another model agreed
Report a problem with this finding
Wording In the same bound, the second term "2^m C^m |z|^m/m^m (Σ_{k≥1} 2^{-k} e^{-t/2^k})" has no m-th power on the sum, yet the next step integrates it as Γ_m (22), which carries the power m.
- p. 11 Proof of Prop. 3, bound on |G|^m and definition (22)
2mCm |z|m/mm (Σk≥1 1/2k e−t/2k)
- p. 11 Proof of Proposition 3, bound on |G(z/m,t)|^m
+ 2mCm |z|m/mm ( Σ k≥1 1/2k e−t/2k )
- p. 11 Equation (22)
Γm :=
Only the authors can say what is right here.
Judge's note: The p.11 image shows the large parentheses with no superscript, while (22) directly below has the power m. Because Σ 2^{-k}e^{-t/2^k} ≤ 1, the printed inequality is true but weaker. Integrated over t, though, the unpowered sum diverges (each term integrates to 1), so the step 'since the integral Γ_m converges, we obtain' does not follow from the inequality as printed. The exponent m needs restoring. The result is unchanged.
Second check: another model agreed
Report a problem with this finding
Wording The Fig. 4 note says the lines "represent the predicted standard error, namely, ... ±0.5% for m = 65536", but 1.04/√65536 ≈ 0.41%. The bottom-right panel draws its lines at about ±5 (×10^-3), so the lines match the note rather than the predicted value.
- p. 16 Fig. 4 caption, top panel note
±0.5% for m = 65536
Only the authors can say what is right here.
Judge's note: I checked the page 16 image. The note reads "±0.5% for m = 65536", and the bottom-right panel has its green lines at about ±5 on a ×10^-3 axis. The paper's own standard-error formula 1.04/√m gives 0.406% for m = 65536. The other two values are close roundings: 6.5%→7% and 3.25%→3%. This one is about 23% above the predicted value. The plot is only illustrative, so this is a minor point for the authors to confirm. The axis unit is also not labelled.
Second check: another model agreed
Report a problem with this finding
Typo "its evaluation function: its is based on harmonic means": 'its is' should read 'it is'.
- p. 3 Introduction, paragraph after Fig. 1
evaluation function: its is based on harmonic means
- p. 3 Introduction, paragraph after Fig. 1
its is based on harmonic means
- p. 3 Introduction, paragraph after Figure 1
its evaluation function: its is based on harmonic means
Judge's note: The page 3 image shows the typo in the typeset text.
Second check: none (judge only)
Report a problem with this finding
Typo "for j = 1 . . . , m": a comma is missing after 1 (should be j = 1, . . . , m).
- p. 4 Text after Eq. (1)
for j = 1 . . . , m
Judge's note: The page 4 image, in the text after Eq. (1), shows the missing comma.
Second check: none (judge only)
Report a problem with this finding
Typo Eq. (25) writes the error term as ϵ'_m(x), but the following text says "where ϵ'(x) is a small oscillating function" (subscript m dropped).
- p. 12 Equation (25) and the following line
where ϵ′(x) is a small oscillating function
Judge's note: The p.12 image confirms the subscript m in (25) and its absence in the text. The meaning is clear.
Second check: none (judge only)
Report a problem with this finding
Typo "Given known fact regarding the coupon collector problem": an article or plural is missing ('Given known facts' / 'Given a known fact').
- p. 13 Section 4 (i) Initialization of registers
Given known fact regarding the coupon collector problem
Judge's note: The p.13 image, Section 4(i), confirms the wording.
Second check: none (judge only)
Report a problem with this finding
Typo The symbol L is reused: "L = log 2" (Sec. 3.2), "hashing over at least L = 32 bits" and "(1 + ϵ)^L = N" on the same page (p.15), and L := ⌊log2(|z|/m)⌋ in the proof of Prop. 3.
- p. 15 Large range corrections vs Optimality considerations
hashing over at least L = 32 bits
- p. 15 Optimality considerations (i)
(1 + ϵ)L = N
- p. 13 Section 3.2
L = log 2
Judge's note: Seen on p.11, p.13 and p.15. Each use is local and recoverable from context, but two different meanings sit within a few lines on p.15.
Second check: none (judge only)
Report a problem with this finding
Typo The Fig. 4 note reads "The top and botton horizontal lines"; "botton" should be "bottom".
- p. 16 Fig. 4, note under the trace panels
The top and botton horizontal lines
Judge's note: The misspelling appears in the page 16 image.
Second check: none (judge only)
Report a problem with this finding
Typo The Fig. 5 caption reads "octal dumps of the postcript source"; "postcript" should be "PostScript".
- p. 17 Fig. 5 caption
octal dumps of the postcript
- p. 17 Fig. 5 caption
octal dumps of the postcript source
- p. 17 Fig. 5 caption
the postcript
- p. 17 Fig. 5 caption
postcript
Judge's note: The misspelling appears in the page 17 image of the Fig. 5 caption.
Second check: none (judge only)