Comment fonctionne l’algorithme HyperLogLog?

J’ai récemment étudié différents algorithmes dans mon temps libre, et celui que j’ai trouvé très intéressant s’appelle l’algorithme HyperLogLog, qui estime combien d’éléments uniques se trouvent dans une liste.

Cela a été particulièrement intéressant pour moi, car cela m’a ramené à mes jours MySQL lorsque j’ai vu la valeur de “cardinalité” (que j’ai toujours supposé jusqu’à récemment qu’elle n’avait pas été calculée).

Je sais donc écrire un algorithme dans O ( n ) qui calculera le nombre d’éléments uniques dans un tableau. J’ai écrit ceci en JavaScript:

function countUniqueAlgo1(arr) { var Table = {}; var numUnique = 0; var numDataPoints = arr.length; for (var j = 0; j < numDataPoints; j++) { var val = arr[j]; if (Table[val] != null) { continue; } Table[val] = 1; numUnique++; } return numUnique; } 

Mais le problème est que mon algorithme, alors que O ( n ), utilise beaucoup de mémoire (stockant des valeurs dans la Table ).

J’ai lu cet article sur la manière de compter les doublons dans une liste en temps O ( n ) et en utilisant un minimum de mémoire.

Il explique qu’en hachant et en comptant des bits ou quelque chose, on peut estimer à l’intérieur d’une certaine probabilité (en supposant que la liste est uniformément répartie) le nombre d’éléments uniques dans une liste.

J’ai lu le journal, mais je n’arrive pas à le comprendre. Quelqu’un peut-il donner une explication plus laïque? Je sais ce que sont les hachages, mais je ne comprends pas comment ils sont utilisés dans cet algorithme HyperLogLog.

Le principal truc derrière cet algorithme est que si vous observez un stream d’entiers aléatoires voir un entier dont la représentation binary commence avec un préfixe connu, il y a plus de chance que la cardinalité du stream soit 2 ^ (taille du préfixe) .

Autrement dit, dans un stream aléatoire d’entiers, ~ 50% des nombres (en binary) commencent par “1”, 25% commencent par “01”, 12,5% commencent par “001”. Cela signifie que si vous observez un stream aléatoire et voyez un “001”, il y a plus de chance que ce stream ait une cardinalité de 8.

(Le préfixe “00..1” n’a pas de signification particulière. C’est juste parce qu’il est facile de trouver le bit le plus significatif dans un nombre binary dans la plupart des processeurs)

Bien sûr, si vous observez un seul entier, la probabilité que cette valeur soit erronée est élevée. C’est pourquoi l’algorithme divise le stream en “m” sous-stream indépendants et conserve la longueur maximale d’un préfixe “00 … 1” de chaque sous-stream. Ensuite, estime la valeur finale en prenant la valeur moyenne de chaque sous-stream.

C’est l’idée principale de cet algorithme. Il manque des détails (la correction pour les valeurs d’estimation faibles, par exemple), mais tout est bien écrit dans le papier. Désolé pour le terrible anglais.

Un HyperLogLog est une structure de données probabiliste . Il compte le nombre d’éléments distincts dans une liste. Mais par rapport à une manière simple de le faire (avoir un ensemble et append des éléments à l’ensemble), il le fait de manière approximative.

Avant de voir comment l’algorithme HyperLogLog fait cela, il faut comprendre pourquoi vous en avez besoin. Le problème est simple: il consum O(distinct elements) de l’espace. Pourquoi y a-t-il une grande notation O ici plutôt que des éléments distincts? C’est parce que les éléments peuvent être de tailles différentes. Un élément peut être 1 un autre élément "is this big ssortingng" . Donc, si vous avez une liste énorme (ou un énorme stream d’éléments), il faudra beaucoup de mémoire.


Comptage probabiliste

Comment peut-on obtenir une estimation raisonnable d’un certain nombre d’éléments uniques? Supposons que vous ayez une chaîne de longueur m composée de {0, 1} avec une probabilité égale. Quelle est la probabilité qu’il commence par 0, avec 2 zéros, avec k zéros? C’est 1/2 , 1/4 et 1/2 1/2^k . Cela signifie que si vous avez rencontré une chaîne avec k zéros, vous avez parcouru approximativement 2^k éléments. C’est donc un bon sharepoint départ. Ayant une liste d’éléments uniformément répartis entre 0 et 2^k - 1 vous pouvez compter le nombre maximum du plus grand préfixe de zéros dans la représentation binary, ce qui vous donnera une estimation raisonnable.

Le problème est que l’hypothèse de la dissortingbution régulière des nombres de 0 t 2^k-1 est trop difficile à obtenir (les données que nous avons rencontrées ne sont généralement pas des nombres, elles ne sont presque jamais dissortingbuées et peuvent être entre des valeurs quelconques). fonction de hachage, vous pouvez supposer que les bits de sortie sont dissortingbués de manière uniforme et que la plupart des fonctions de hachage ont des sorties comsockets entre 0 et 2^k - 1 ( SHA1 vous donne des valeurs entre 0 et 2^160 ). peut estimer le nombre d’éléments uniques avec la cardinalité maximale de k bits en ne stockant qu’un seul nombre de bits de taille log(k) . L’inconvénient est que notre estimation varie énormément. papier (il est un peu plus intelligent avec l’estimation, mais nous sums toujours proches).

LogLog

Avant d’aller plus loin, nous devons comprendre pourquoi notre première estimation n’est pas très bonne. La raison en est qu’une occurrence aléatoire d’un élément à préfixe 0 haute fréquence peut tout gâcher. Une des façons de l’améliorer consiste à utiliser de nombreuses fonctions de hachage, à savoir compter au maximum pour chacune des fonctions de hachage et à la fin, les en extraire. C’est une excellente idée, qui améliorera l’estimation, mais le papier LogLog a utilisé une approche légèrement différente (probablement parce que le hachage est un peu coûteux).

Ils ont utilisé un hash mais l’ont divisé en deux parties. L’un s’appelle un seau (le nombre total de seaux est 2^x ) et un autre – est fondamentalement le même que notre hachage. C’était difficile pour moi d’obtenir ce qui se passait, alors je vais donner un exemple. Supposons que vous ayez deux éléments et que votre fonction de hachage qui donne des valeurs de 0 à 2^10 produise 2 valeurs: 344 et 387 . Vous avez décidé d’avoir 16 seaux. Donc, vous avez:

 0101 011000 bucket 5 will store 1 0110 000011 bucket 6 will store 4 

En ayant plus de godets, vous diminuez la variance (vous utilisez un peu plus d’espace, mais c’est encore petit). En utilisant les compétences en mathématiques, ils ont pu quantifier l’erreur (qui est de 1.3/sqrt(number of buckets) ).

HyperLogLog

HyperLogLog n’introduit pas de nouvelles idées, mais utilise surtout beaucoup de calculs pour améliorer l’estimation précédente. Les chercheurs ont constaté que si vous retirez 30% des plus gros nombres des seaux, vous améliorez considérablement l’estimation. Ils ont également utilisé un autre algorithme pour calculer la moyenne des nombres. Le papier est lourd en mathématiques.


Et je veux terminer avec un article récent, qui montre une version améliorée de l’algorithme hyperLogLog (jusqu’à présent, je n’avais pas le temps de le comprendre, mais peut-être que je pourrai améliorer cette réponse plus tard).

L’intuition est que si votre entrée est un grand ensemble de nombres aléatoires (par exemple, des valeurs hachées), elles doivent être réparties uniformément sur une plage. Disons que la plage peut aller jusqu’à 10 bits pour représenter la valeur jusqu’à 1024. Ensuite, nous avons observé la valeur minimale. Disons que c’est 10. Alors la cardinalité sera estimée à environ 100 (10 × 100 ≈ 1024).

Lisez le papier pour la vraie logique du cours.

Une autre bonne explication avec un exemple de code peut être trouvée ici:
Algorithmes de Damn Cool: estimation de cardinalité – Nick’s Blog