HyperLogLog
Structure de données probabiliste qui compte les éléments distincts d'un flux avec une mémoire constante — Flajolet et al. (2007). 12 Ko suffisent pour dénombrer des milliards d'éléments uniques avec une erreur de l'ordre de 1 à 2 %.
L'astuce : on hache les clés, puis on compte les zéros de tête du hachage binaire — la plus longue série en dit long sur le nombre de valeurs uniques rencontrées (plus il y en a, plus on a de chances de tomber sur une longue série de zéros). Une médiane sur m « cases » réduit la variance.
Sert de moteur au PFCOUNT de Redis, aux décomptes distincts approximatifs de Presto/Trino, à BigQuery et à Druid. Gain face à un count(distinct) exact : on passe de méga-octets de mémoire par requête à des kilo-octets, avec des résultats fusionnables d'une partition à l'autre.