HyperLogLog¶
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science Proceedings AH (Conference on Analysis of Algorithms), 137-156.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Cardinality
- The platform is a direct, high-volume industrial transfer of Cantorian cardinality into database systems engineering at a scale Cantor could not have anticipated.
This sourceSingle-pass probabilistic distinct-count algorithm using O(log log n) auxiliary memory with relative standard error ≈ 1.04/√m; the canonical industrial transfer of cardinality into streaming analytics (the ~12 KB / 10⁹-cardinality / ~2% figure follows from this accuracy law).
Supported in partVerified against the publisher's abstract
HyperLogLog's own abstract backs large-scale single-pass cardinality estimation (beyond 10^9 at 2% in 1.5 KB); it says nothing of Cantorian cardinality or an industrial transfer.
“For instance, the new algorithm makes it possible to estimate cardinalities well beyond $10^9$ with a typical accuracy of 2% while using a memory of only 1.5 kilobytes.”
- The platform is a direct, high-volume industrial transfer of Cantorian cardinality into database systems engineering at a scale Cantor could not have anticipated.
- Monoid
- Distinct users is a monoid under set union with a carrier too large to ship, so union is replaced by sketch merge, associative and commutative with the empty sketch as unit, trading exactness for a bounded carrier that still satisfies the laws.
This sourceGives a bounded-size sketch for distinct counting and states that under an arbitrary partitioning of the input it suffices to collect register values and apply a componentwise max, an associative and commutative merge with the empty sketch as unit.
Supported in partVerified against the publisher's abstract
Flajolet et al.'s abstract supplies a bounded-memory single-pass sketch for counting distinct elements, but not the monoid framing, the merge laws, or the empty-sketch unit.
“Using an auxiliary memory of m units (typically, "short bytes''), HYPERLOGLOG performs a single pass over the data and produces an estimate of the cardinality such that the relative accuracy (the standard error) is typically about $1.04/\sqrt{m}$.”
- Distinct users is a monoid under set union with a carrier too large to ship, so union is replaced by sketch merge, associative and commutative with the empty sketch as unit, trading exactness for a bounded carrier that still satisfies the laws.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 2 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:87e826a81b0c · see in the full table