Algorithme de Flajolet et Martin

L'algorithme nécessite une fonction de hashage ${\displaystyle hash(x)}$, associant à une entrée ${\displaystyle x}$ un entier dans ${\displaystyle [0,2^{L}-1]}$, dont les images sont uniformément réparties. L'ensemble des entiers de 0 à ${\displaystyle 2^{L}-1}$ correspond en fait à l'ensemble des chaînes binaires de longueur ${\displaystyle L}$.

Étant donné un entier positif ${\displaystyle y}$, on note ${\displaystyle bit(y,k)}$ le ${\displaystyle k}$-ème bit dans la représentation binaire de ${\displaystyle y}$, de sorte que :

${\displaystyle y=\sum _{k\geq 0}{\text{bit}}(y,k)2^{k}}$

On définit ensuite une fonction ${\displaystyle \rho (y)}$ qui associe à y la position du bit de poids faible dans sa représentation binaire :

${\displaystyle \rho (y)=\min _{k\geq 0}{\text{bit}}(y,k)\neq 0}$

avec ${\displaystyle \rho (0)=L}$. Par exemple, ${\displaystyle \rho (13)=\rho (1101)=0}$ car le premier bit est non nul, alors que ${\displaystyle \rho (8)=\rho (0100)=2}$ avec le bit de poids faible en troisième position. Étant donné que les images de la fonction de hashage sont uniformément réparties, la probabilité d'observer un nombre finissant par ${\displaystyle 2^{k}}$ (un 1 suivi de ${\displaystyle k}$ zéros) est ${\displaystyle 2^{-(k+1)}}$ et correspond à tirer ${\displaystyle k}$ piles suivi d'un face en lançant une pièce de monnaie équilibrée.

• HyperLogLog

• (en) Anand Rajaraman et Jeffrey David Ullman, Mining of Massive Datasets, Cambridge University Press, 27 octobre 2011, 119 p. (ISBN 978-1-139-50534-5, lire en ligne)
• « Vidéo du cours au collège de France de Claire Mathieu sur le sujet », 16 janvier 2018