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
- … Cohen 1963 independence via forcing), exposing a foundational gap in the standard axiomatization of set theory; large-cardinal axioms (inaccessible, Mahlo, measurable, supercompact, Reinhardt) extend ZFC by postulating cardinals of ever-greater consistency strength; (4) the concept generalises across domains —
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).
- … Cohen 1963 independence via forcing), exposing a foundational gap in the standard axiomatization of set theory; large-cardinal axioms (inaccessible, Mahlo, measurable, supercompact, Reinhardt) extend ZFC by postulating cardinals of ever-greater consistency strength; (4) the concept generalises across domains —
- 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.
- 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¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:87e826a81b0c · see in the full table