HyperLogLog
HyperLogLog approximiert die Kardinalität (Distinct-Count) aus führenden Nullen von Hashwerten und schätzt riesige Distinct-Anzahlen in kleinem festem Speicher.
Zweck
Ungefähr Milliarden unterschiedlicher Elemente in festem Speicher (~KB) zählen, genutzt für Unique-Visitor-Statistiken.
Mechanismus
Jedes Element wird gehasht, nach den ersten k Bits in Buckets einsortiert, und pro Bucket wird die maximale Anzahl führender Nullen der restlichen Bits vermerkt. Die Kardinalitätsschätzung ≈ α·m²·∑2^M[i]. Der relative Fehler liegt bei etwa 1.04/√m. Redis PFCOUNT nutzt dies.
Anwendungsfälle
- Unique-Visitor-Statistiken
- Kardinalitätsschätzung
- Distinct-Counting in Streams