HyperLogLog
HyperLogLog approxime la cardinalité (comptage de valeurs distinctes) à partir des zéros de tête des valeurs de hachage, estimant d'énormes comptages distincts dans une petite mémoire fixe.
Objectif
Compter approximativement des milliards d'éléments distincts en mémoire fixe (~Ko), utilisé pour les statistiques de visiteurs uniques.
Mécanisme
On hache chaque élément, on répartit par les k premiers bits et on enregistre dans chaque seau le nombre maximal de zéros de tête parmi les bits restants. L'estimation de cardinalité ≈ α·m²·∑2^M[i]. L'erreur relative est d'environ 1.04/√m. Redis PFCOUNT l'utilise.
Cas d’usage
- Statistiques de visiteurs uniques
- Estimation de cardinalité
- Comptage distinct en flux