Article de reference

HyperLogLog

Terminologie Dans l'article original de Flajolet et al. et dans la littérature relative au problème du comptage des éléments distincts , le terme « cardinalité » désigne le nomb...

Worldlex WikiFrancaisLecture gratuite

Terminologie

Dans l'article original de Flajolet et al. et dans la littérature relative au problème du comptage des éléments distincts , le terme « cardinalité » désigne le nombre d'éléments distincts dans un flux de données comportant des éléments répétés. Cependant, dans la théorie des multiensembles, ce terme fait référence à la somme des multiplicités de chaque élément d'un multiensemble. Par souci de cohérence avec les sources, cet article adopte la définition de Flajolet.

Algorithme

L'algorithme HyperLogLog repose sur le constat que la cardinalité d'un multiensemble de nombres aléatoires uniformément distribués peut être estimée en calculant le nombre maximal de zéros non significatifs dans la représentation binaire de chaque nombre de l'ensemble. Si ce nombre maximal est n , on estime le nombre d'éléments distincts de l'ensemble à 2 ^n .

Dans l'algorithme HyperLogLog, une fonction de hachage est appliquée à chaque élément du multiensemble initial afin d'obtenir un multiensemble de nombres aléatoires uniformément distribués, de même cardinalité que le multiensemble initial. La cardinalité de cet ensemble aléatoire peut ensuite être estimée à l'aide de l'algorithme décrit précédemment.

L'estimation simple de la cardinalité obtenue à l'aide de l'algorithme ci-dessus présente l'inconvénient d'une variance élevée . Dans l'algorithme HyperLogLog, la variance est minimisée en divisant le multiensemble en de nombreux sous-ensembles, en calculant le nombre maximal de zéros non significatifs dans les nombres de chacun de ces sous-ensembles, et en utilisant une moyenne harmonique pour combiner ces estimations pour chaque sous-ensemble afin d'obtenir une estimation de la cardinalité de l'ensemble entier.

Opérations

L'HyperLogLog possède trois opérations principales : ajouter pour insérer un nouvel élément dans l'ensemble, compter pour obtenir sa cardinalité et fusionner pour obtenir l'union de deux ensembles. Certaines opérations dérivées peuvent être calculées à l'aide du principe d'inclusion-exclusion, comme la cardinalité de l'intersection ou la cardinalité de la différence entre deux HyperLogLogs, en combinant les opérations de fusion et de comptage.

Les données de l'HyperLogLog sont stockées dans un tableau compteurs (ou « registres ») qui sont initialisés à 0. Le tableau est appelé croquis HyperLogLog de S.

Ajouter

L'opération d'addition consiste à calculer le hachage des données d'entrée , en obtenant les est ${ extstyle \log _{2}(m) <semantics><mrow><mstyle><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mo>(</mo><mi>m</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle \log _{2}(m)}</annotation></semantics></math><img src=$ ${ extstyle ho (w) </span referrerpolicy=$ qui renvoie la position du 1 le plus à gauche, où la position la plus à gauche est 1 (autrement dit : nombre de zéros non significatifs plus 1). La nouvelle valeur du registre sera la valeur maximale entre la valeur actuelle du registre et ${ extstyle ho (w) <semantics><mrow><mstyle><mi>ρ</mi><mo>(</mo><mi>w</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle ho (w)}</annotation></semantics></math><img src=$

{\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b} angle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j], ho (w))\\\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>x</mi></mtd><mtd><mi></mi><mo>:=</mo><mi>h</mi><mo>(</mo><mi>v</mi><mo>)</mo></mtd></mtr><mtr><mtd><mi>j</mi></mtd><mtd><mi></mi><mo>:=</mo><mn>1</mn><mo>+</mo><mo>⟨</mo><msub><mi>x</mi><mrow><mn>1</mn></mrow></msub><msub><mi>x</mi><mrow><mn>2</mn></mrow></msub><mo>.</mo><mo>.</mo><mo>.</mo><msub><mi>x</mi><mrow><mi>b</mi></mrow></msub><msub><mo>⟩</mo><mrow><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><mi>w</mi></mtd><mtd><mi></mi><mo>:=</mo><msub><mi>x</mi><mrow><mi>b</mi><mo>+</mo><mn>1</mn></mrow></msub><msub><mi>x</mi><mrow><mi>b</mi><mo>+</mo><mn>2</mn></mrow></msub><mo>.</mo><mo>.</mo><mo>.</mo></mtd></mtr><mtr><mtd><mi>M</mi><mo>[</mo><mi>j</mi><mo>]</mo></mtd><mtd><mi></mi><mo>:=</mo><mo>max</mo><mo>(</mo><mi>M</mi><mo>[</mo><mi>j</mi><mo>]</mo><mo>,</mo><mi>ρ</mi><mo>(</mo><mi>w</mi><mo>)</mo><mo>)</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}x&:=h(v)\\j&:=1+\langle x_{1}x_{2}...x_{b} angle _{2}\\w&:=x_{b+1}x_{b+2}...\\M[j]&:=\max(M[j], ho (w))\\\end{aligned}}}</annotation></semantics></math></span><img src=

Compter

L'algorithme de comptage consiste à calculer la moyenne harmonique des ${ extstyle E </span referrerpolicy=$ du comté :

{\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1 <semantics><mrow><mstyle><mi>Z</mi><mo>=</mo><mrow><mrow><mo>(</mo></mrow></mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>m</mi></mrow></munderover><mrow><msup><mn>2</mn><mrow><mo>−</mo><mi>M</mi><mo>[</mo><mi>j</mi><mo>]</mo></mrow></msup></mrow><msup><mrow><mrow><mo>)</mo></mrow></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle Z={\Bigg (}\sum _{j=1}^{m}{2^{-M[j]}}{\Bigg )}^{-1}}</annotation></semantics></math></span><img src=

{\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}} ight) ight)^{m}\,du ight)^{-1 <semantics><mrow><mstyle><msub><mi>α</mi><mrow><mi>m</mi></mrow></msub><mo>=</mo><msup><mrow><mo>(</mo><mrow><mi>m</mi><msubsup><mo>∫</mo><mrow><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></msubsup><msup><mrow><mo>(</mo><mrow><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mfrac><mrow><mn>2</mn><mo>+</mo><mi>vous</mi></mrow><mrow><mn>1</mn><mo>+</mo><mi>vous</mi></mrow></mfrac></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mrow><mi>m</mi></mrow></msup><mspace></mspace><mi>d</mi><mi>vous</mi></mrow><mo>)</mo></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup></mstyle></mrow><annotation>{\displaystyle \alpha _{m}=\left(m\int _{0}^{\infty }\left(\log _{2}\left({\frac {2+u}{1+u}} ight) ight)^{m}\,du ight)^{-1}}</annotation></semantics></math></span><img src=

{\displaystyle E=\alpha _{m}m^{2}Z <semantics><mrow><mstyle><mi>E</mi><mo>=</mo><msub><mi>α</mi><mrow><mi>m</mi></mrow></msub><msup><mi>m</mi><mrow><mn>2</mn></mrow></msup><mi>Z</mi></mstyle></mrow><annotation>{ displaystyle E = alpha _ {m} m ^ {2} Z}</annotation></semantics></math></span><img src=

L'intuition est que , chaque sous-ensemble ${ extstyle M_{j <semantics><mrow><mstyle><msub><mi>M</mi><mrow><mi>j</mi></mrow></msub></mstyle></mrow><annotation>{ extstyle M_{j}}</annotation></semantics></math><img src=$ ${ extstyle n/m <semantics><mrow><mstyle><mi>n</mi><mrow><mo>/</mo></mrow><mi>m</mi></mstyle></mrow><annotation>{ extstyle n/m}</annotation></semantics></math><img src=$ ${ extstyle \max _{x\in M_{j}} ho (x) <semantics><mrow><mstyle><munder><mo>max</mo><mrow><mi>x</mi><mo>∈</mo><msub><mi>M</mi><mrow><mi>j</mi></mrow></msub></mrow></munder><mi>ρ</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle \max _{x\in M_{j}} ho (x)}</annotation></semantics></math><img src=$ ${ extstyle \log _{2}(n/m) <semantics><mrow><mstyle><msub><mi>enregistrer</mi><mrow><mn>2</mn></mrow></msub><mo>⁡</mo><mo>(</mo><mi>n</mi><mrow><mo>/</mo></mrow><mi>m</mi><mo>)</mo></mstyle></mrow><annotation>{ extstyle \log _{2}(n/m)}</annotation></semantics></math><img src=$ ${ extstyle mZ <semantics><mrow><mstyle><mi>m</mi><mi>Z</mi></mstyle></mrow><annotation>{ extstyle mZ}</annotation></semantics></math><img src=$ ${ extstyle n/m <semantics><mrow><mstyle><mi>n</mi><mrow><mo>/</mo></mrow><mi>m</mi></mstyle></mrow><annotation>{ extstyle n/m}</annotation></semantics></math><img src=$ ${ extstyle m^{2}Z <semantics><mrow><mstyle><msup><mi>m</mi><mrow><mn>2</mn></mrow></msup><mi>Z</mi></mstyle></mrow><annotation>{ extstyle m^{2}Z}</annotation></semantics></math><img src=$ ${ extstyle \alpha _{m <mrow><mstyle><msup><mi>m</mi><mrow><mn>2</mn></mrow></msup><mi>Z</mi></mstyle></mrow><annotation>{ extstyle m^{2}Z}</annotation></semantics></math><img src=$

Considérations pratiques

La constante ${ extstyle \alpha _{m <semantics><mrow><mstyle><msub><mi>α</mi><mrow><mi>m</mi></mrow></msub></mstyle></mrow><annotation>{ extstyle \alpha _{m}}</annotation></semantics></math><img src=$

{\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{ ext{for }}m=16;\\0.697,&{ ext{for }}m=32;\\0.709,&{ ext{for }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{ ext{for }}m\geq 128.\end{cases <semantics><mrow><mstyle><msub><mi>α</mi><mrow><mi>m</mi></mrow></msub><mo>≈</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mn>0,673</mn><mo>,</mo></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>=</mo><mn>16</mn><mo>;</mo></mtd></mtr><mtr><mtd><mn>0,697</mn><mo>,</mo></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>=</mo><mn>32</mn><mo>;</mo></mtd></mtr><mtr><mtd><mn>0,709</mn><mo>,</mo></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>=</mo><mn>64</mn><mo>;</mo></mtd></mtr><mtr><mtd><mrow><mfrac><mn>0,7213</mn><mrow><mn>1</mn><mo>+</mo><mn>1,079</mn><mrow><mo>/</mo></mrow><mi>m</mi></mrow></mfrac></mrow><mo>,</mo></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>≥</mo><mn>128.</mn></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle \alpha _{m}\approx {\begin{cases}0.673,&{ ext{pour }}m=16;\\0.697,&{ ext{pour }}m=32;\\0.709,&{ ext{pour }}m=64;\\{\frac {0.7213}{1+1.079/m}},&{ ext{pour }}m\geq 128.\end{cases}}}</annotation></semantics></math></span><img src=

La technique HyperLogLog, cependant, est biaisée pour les petites cardinalités inférieures à un seuil de ${ extstyle {\frac {5}{2}}m <semantics><mrow><mstyle><mrow><mfrac><mn>5</mn><mn>2</mn></mfrac></mrow><mi>m</mi></mstyle></mrow><annotation>{ extstyle {\frac {5}{2}}m}</annotation></semantics></math><img src=$ ${ extstyle E<{\frac {5}{2}}m <semantics><mrow><mstyle><mi>E</mi><mo><</mo><mrow><mfrac><mn>5</mn><mn>2</mn></mfrac></mrow><mi>m</mi></mstyle></mrow><annotation>{ extstyle E<{\frac {5}{2}}m}</annotation></semantics></math><img src=$

Laisser ${ extstyle V <semantics><mrow><mstyle><mi>V</mi></mstyle></mrow><annotation>{ extstyle V}</annotation></semantics></math><img src=$
Si ${ extstyle V=0 <semantics><mrow><mstyle><mi>V</mi><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{ extstyle V=0}</annotation></semantics></math><img src=$ ${ extstyle E <semantics><mrow><mstyle><mi>E</mi></mstyle></mrow><annotation>{ extstyle E}</annotation></semantics></math><img src=$
Sinon, utilisez le comptage linéaire : ${ extstyle E^{\star }=m\log \left({\frac {m}{V}} ight) <semantics><mrow><mstyle><msup><mi>E</mi><mrow><mo>⋆</mo></mrow></msup><mo>=</mo><mi>m</mi><mi>enregistrer</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mfrac><mi>m</mi><mi>V</mi></mfrac></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{ extstyle E^{\star }=m\log \left({\frac {m}{V}} ight)}</annotation></semantics></math><img src=$

De plus, pour des cardinalités très élevées approchant la limite de la taille des registres ( ${\frac {2^{32}}{30 E > \frac{2^{32}}{30}$ {\frac {2^{32}}{30 (pour les registres 32 bits), la cardinalité peut être estimée avec :

{\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}} ight) <semantics><mrow><mstyle><msup><mi>E</mi><mrow><mo>⋆</mo></mrow></msup><mo>=</mo><mo>−</mo><msup><mn>2</mn><mrow><mn>32</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mrow><mfrac><mi>E</mi><msup><mn>2</mn><mrow><mn>32</mn></mrow></msup></mfrac></mrow></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle E^{\star }=-2^{32}\log \left(1-{\frac {E}{2^{32}}} ight)}</annotation></semantics></math></span><img src=

Avec les corrections ci-dessus pour les bornes inférieure et supérieure, l'erreur peut être estimée comme suit : ${ extstyle \sigma =1.04/{\sqrt {m <semantics><mrow><mstyle><mi>σ</mi><mo>=</mo><mn>1.04</mn><mrow><mo>/</mo></mrow><mrow><msqrt><mi>m</mi></msqrt></mrow></mstyle></mrow><annotation>{ extstyle \sigma =1.04/{\sqrt {m}}}</annotation></semantics></math><img src=$

Fusionner

L'opération de fusion pour deux HLL ( ${ extstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2 <semantics><mrow><mstyle><msub><mrow><mrow><mi>h</mi><mi>l</mi><mi>l</mi></mrow></mrow><mrow><mn>1</mn></mrow></msub><mo>,</mo><msub><mrow><mrow><mi>h</mi><mi>l</mi><mi>l</mi></mrow></mrow><mrow><mn>2</mn></mrow></msub></mstyle></mrow><annotation>{ extstyle {\mathit {hll}}_{1},{\mathit {hll}}_{2}}</annotation></semantics></math><img src=$ ${ extstyle j:1..m <semantics><mrow><mstyle><mi>j</mi><mo>:</mo><mn>1..</mn><mi>m</mi></mstyle></mrow><annotation>{ extstyle j:1..m}</annotation></semantics></math><img src=$

{\displaystyle {\mathit {hll}}_{ ext{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j]) <semantics><mrow><mstyle><msub><mrow><mrow><mi>h</mi><mi>l</mi><mi>l</mi></mrow></mrow><mrow><mtext>union</mtext></mrow></msub><mo>[</mo><mi>j</mi><mo>]</mo><mo>=</mo><mo>max</mo><mo>(</mo><msub><mrow><mrow><mi>h</mi><mi>l</mi><mi>l</mi></mrow></mrow><mrow><mn>1</mn></mrow></msub><mo>[</mo><mi>j</mi><mo>]</mo><mo>,</mo><msub><mrow><mrow><mi>h</mi><mi>l</mi><mi>l</mi></mrow></mrow><mrow><mn>2</mn></mrow></msub><mo>[</mo><mi>j</mi><mo>]</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle {\mathit {hll}}_{ ext{union}}[j]=\max({\mathit {hll}}_{1}[j],{\mathit {hll}}_{2}[j])}</annotation></semantics></math></span><img src=

Complexité

Pour analyser la complexité, le flux de données ${\displaystyle (\epsilon ,\delta ) <semantics><mrow><mstyle><mo>(</mo><mi>ϵ</mi><mo>,</mo><mi>δ</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle (\epsilon ,\delta )}</annotation></semantics></math><img src=$ ${\displaystyle 1\pm \epsilon <semantics><mrow><mstyle><mn>1</mn><mo>±</mo><mi>ϵ</mi></mstyle></mrow><annotation>{\displaystyle 1\pm \epsilon }</annotation></semantics></math><img src=$ ${\displaystyle 1-\delta <semantics><mrow><mstyle><mn>1</mn><mo>−</mo><mi>δ</mi></mstyle></mrow><annotation>{\displaystyle 1-\delta }</annotation></semantics></math><img src=$ ${\displaystyle 1.04/{\sqrt {m <semantics><mrow><mstyle><mn>1.04</mn><mrow><mo>/</mo></mrow><mrow><msqrt><mi>m</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle 1.04/{\sqrt {m}}}</annotation></semantics></math><img src=$ ${\displaystyle O(\epsilon ^{-2}\log \log n+\log n) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><msup><mi>ϵ</mi><mrow><mo>−</mo><mn>2</mn></mrow></msup><mi>enregistrer</mi><mo>⁡</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>+</mo><mi>enregistrer</mi><mo>⁡</mo><mi>n</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(\epsilon ^{-2}\log \log n+\log n)}</annotation></semantics></math><img src=$

L' opération d'addition dépend de la taille de la sortie de la fonction de hachage. Cette taille étant fixe, on peut considérer que le temps d'exécution de l'opération d'addition est ${\displaystyle O(1) <semantics><mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(1)}</annotation></semantics></math><img src=$

Les opérations de comptage et de fusion dépendent du nombre de registres ${\displaystyle O(m) <mrow><mstyle><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mstyle></mrow><annotation>{\displaystyle O(1)}</annotation></semantics></math><img src=$

HLL++

L'algorithme HyperLogLog++ propose plusieurs améliorations à l'algorithme HyperLogLog pour réduire les besoins en mémoire et augmenter la précision dans certaines plages de cardinalités :

Une fonction de hachage 64 bits est utilisée au lieu des 32 bits employés dans l'article original. Cela réduit les collisions de hachage pour les grandes cardinalités, permettant ainsi de supprimer la correction pour les grandes plages de valeurs.
Un biais est constaté pour les petits ensembles de valeurs lors du passage du comptage linéaire au comptage HLL. Une correction empirique de ce biais est proposée pour atténuer ce problème.
Une représentation clairsemée des registres est proposée pour réduire les besoins en mémoire pour les petites cardinalités, qui peut être transformée ultérieurement en une représentation dense si la cardinalité augmente.

Streaming HLL

Lorsque les données arrivent en flux unique, l' estimateur de probabilité inverse historique ou de martingale améliore significativement la précision de l'estimation HLL et utilise 36 % de mémoire en moins pour atteindre un niveau d'erreur donné. Cet estimateur est optimal pour toute estimation de comptage distinct approximative insensible aux doublons sur un flux unique.

Le scénario à flux unique entraîne également des variantes dans la construction du sketch HLL. HLL-TailCut+ utilise 45 % de mémoire en moins que le sketch HLL d'origine, mais au prix d'une dépendance à l'ordre d'insertion des données et de l'impossibilité de fusionner les sketches.

Pour en savoir plus

« Nouveaux algorithmes d'estimation de cardinalité pour les esquisses HyperLogLog » (PDF) .