La série sur les algorithmes d’estimation du nombre de valeurs distinctes dans un multi-ensemble continue avec un article sur l’algorithme state of the art HyperLogLog. Toutes les idées qui se cachent derrière cet algorithme viennent toutefois de LogLog, décrit plus tôt : si tu veux lire la suite, assure-toi donc de bien connaître LogLog.

L’algorithme LogLog avait deux problèmes principaux :

Valeurs aberrantes

L’estimation finale de LogLog est très sensible aux valeurs aberrantes, c’est-à-dire aux valeurs très éloignées des autres. Il arrive en effet typiquement que la plupart des longueurs maximales de suffixes nuls de chaque paquet soient à peu près égales, par exemple entre 12 et 15, puis, boum, un suffixe nul a une longueur de 27. Ce grand écart sème le désordre dans l’estimation finale du nombre de valeurs distinctes, car la moyenne arithmétique classique s’en accommode mal. En gros, c’est le même principe que lorsque quelques cadres dirigeants et patrons font monter le salaire moyen du pays avec leurs gros salaires.

Les auteurs de l’algorithme ont essayé de régler cela en se débarrassant des valeurs aberrantes : ils ne comptaient pas dans la moyenne quelques-uns des maxima les plus élevés, mais ce n’était pas une très bonne solution. Plus tard, ils ont essayé une autre méthode : à la place de la moyenne arithmétique, ils ont utilisé la moyenne harmonique, qui a de bien meilleures propriétés quand certaines valeurs sont éloignées de la moyenne.

Très mauvais résultats pour les petites cardinalités

LogLog donne des résultats épouvantables quand il doit estimer la cardinalité de petits multi-ensembles. Si le multi-ensemble contient seulement quelques valeurs distinctes, LogLog renvoie une estimation absurdement grande. Les auteurs ont résolu cela astucieusement : quand l’entrée est un multi-ensemble de faible cardinalité, on n’utilise pas l’algorithme LogLog, mais un tout autre algorithme, le bon vieux Linear counting. Oui, mais comment savoir que l’entrée est un multi-ensemble de faible cardinalité, alors que nous ne connaissons justement pas la cardinalité ?

Nous laissons LogLog estimer le nombre de valeurs distinctes et, si nous constatons que cette estimation est relativement basse, nous la jetons et nous la recalculons avec l’algorithme Linear counting. Rappelons rapidement comment fonctionne Linear counting. Au début, nous allouons un tableau de bits nuls d’une taille fixée à l’avance, typiquement une puissance de deux. Nous parcourons tous les éléments du multi-ensemble, nous calculons leur empreinte et nous la convertissons en un entier i compris entre 0 et la longueur du tableau moins 1. À l’indice i, nous stockons alors un un dans le tableau. Enfin, nous comptons les zéros et les uns du tableau et nous estimons la cardinalité grâce à une formule simple.

L’algorithme LogLog, lui, n’utilise aucun tableau de bits dans lequel il « stockerait » les empreintes calculées. Il utilise à la place un tableau dans lequel il garde les longueurs maximales des suffixes. Le tableau peut par exemple ressembler à ceci :

[2, 5, 9, 0, 5, 4, 4, 0]

où chaque nombre indique la longueur maximale du suffixe nul dans le paquet correspondant d’empreintes calculées. Une valeur non nulle en position i signifie alors nécessairement qu’il existe parmi les valeurs du multi-ensemble un élément dont l’empreinte (de trois bits) est égale à i. Autrement dit, nous pouvons convertir ce tableau en tableau de bits pour le linear counting en laissant les zéros et en remplaçant tout nombre strictement positif par un un. À partir du tableau précédent, nous obtenons ainsi le tableau de bits :

[1, 1, 1, 0, 1, 1, 1, 0]

Nous pouvons maintenant appliquer l’algorithme Linear counting et estimer la cardinalité à l’aide de celui-ci.

Il y a toutefois un petit problème. Nous stockons dans le tableau le suffixe nul maximal, mais que se passe-t-il si, dans un paquet, toutes les empreintes se terminent par un un ? Si par exemple nous utilisons les trois derniers bits comme identifiant du paquet auquel appartient l’empreinte, alors la longueur du suffixe nul de l’empreinte « 01001100 » serait zéro, car le vecteur « 01001 » se termine par un 1. Dans le tableau des maxima, nous stockerions donc un zéro à l’indice 4 (100₂=4₁₀). Dans l’algorithme linear counting, cela se traduirait par le fait que nous n’avons trouvé aucune valeur dont l’empreinte soit quatre, ce qui est faux.

Nous modifions donc l’algorithme pour qu’il ne stocke pas dans le tableau des maxima la longueur du plus long suffixe nul, mais l’indice du « premier un en partant de la droite » (pour être précis, on indexe à partir de un), ce qui revient à ajouter un à la longueur du suffixe nul. Ainsi, un zéro à l’indice i signifie qu’aucune valeur n’a une empreinte égale à i, et un tel tableau peut alors être utilisé pour le linear counting.

Implémentation de HyperLogLog

Pas à pas :

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

La fonction alpha renvoie la correction à appliquer à l’estimation calculée, nous la connaissons déjà de la dernière fois ; seulement, dans le cas de HyperLogLog, alpha a une autre valeur selon le nombre de paquets.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

Une fonction qui renvoie le nombre de bits nuls à la fin d’un nombre.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Une fonction qui parcourt toutes les valeurs, les répartit en num_buckets paquets et calcule pour chaque paquet l’indice du premier un en partant de la droite (la longueur du suffixe nul maximal plus un).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Une fonction légèrement modifiée pour le calcul de l’algorithme Linear counting.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

La fonction principale, qui rassemble le tout. Elle calcule d’abord l’estimation avec le LogLog modifié, en utilisant à la quatrième ligne la moyenne harmonique à la place de la moyenne arithmétique, puis elle applique la correction du Linear counting si l’estimation calculée est inférieure à 2,5 fois le nombre de paquets (dans ce cas, nous nous attendons à ce que l’estimation standard de LogLog soit moins bonne que celle du Linear counting) et s’il y a au moins un zéro dans le tableau des maxima (un tableau qui ne contient que des uns ne peut pas être utilisé dans le Linear counting, voir l’article précédent). Et quels sont les résultats de HyperLogLog ?

Lançons un code de test qui estime la cardinalité d’ensembles de cardinalité successive 10, 100, …, 1 000 000 :

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Résultats :

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Nous voyons que les résultats s’écartent toujours du résultat exact de moins d’un pour cent. Et c’est bien !

Autres améliorations de HyperLogLog

HyperLogLog a connu plusieurs autres améliorations intéressantes. L’un des problèmes restants est la forte consommation de mémoire. Cela paraît bizarre, puisque la dernière fois nous avons porté aux nues sa faible consommation de mémoire et calculé qu’il nous suffit de 768 octets pour stocker le tableau des maxima. Mais le problème apparaît si tu veux calculer non pas la cardinalité d’un seul énorme multi-ensemble, mais celle de plusieurs millions de petits multi-ensembles en parallèle, ou si tu veux conserver ces tableaux de maxima dans une base de données pour d’éventuelles manipulations ultérieures.

Si par exemple nous calculions en même temps la cardinalité d’un milliard de multi-ensembles, il nous faudrait avec l’implémentation actuelle 1 000 000 000 fois 768 octets, soit 768 Go. D’un côté, ce n’est pas mal… mais de l’autre, nous sommes capables d’implémenter HyperLogLog mieux.

Représentation creuse

Imaginons que nous fixons k=12, c’est-à-dire que nous utilisons 12 bits pour identifier les paquets et que nous obtenons donc 2¹² paquets d’empreintes différents. Au début de l’algorithme, nous devons allouer un tableau de longueur 4 096 (voir la ligne 3 de la fonction count_maxims). Supposons que notre multi-ensemble ait trois éléments distincts. Cela signifie que nous donnons une valeur à trois endroits différents du tableau et que les 4 093 autres valeurs du tableau restent nulles : ces 4 093 cases, nous ne les avons tout simplement pas utilisées. Ce n’est pas très efficace, n’est-ce pas ?

Pour éviter d’avoir un tableau en grande partie nul et inutilisé, mais qui occupe quand même un précieux morceau de mémoire, nous pouvons au début stocker les valeurs sous forme de couples [indice, valeur]. Un exemple pour mieux comprendre. Ce tableau

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

peut être représenté de façon bien plus économe en mémoire par deux couples :

[0, 7], [4, 12]

Au lieu d’avoir en mémoire un tas de place inutilisée, nous pouvons allouer progressivement seulement la place dont nous avons vraiment besoin. Cette représentation s’appelle creuse (sparse). À un certain moment, cette représentation deviendrait toutefois plus gourmande en mémoire qu’un simple stockage dans un tableau : nous pouvons alors convertir la représentation creuse en tableau classique sans perte d’information.

Décalages (offsets)

La pratique a montré que toutes les valeurs du tableau sont à peu près égales. Le tableau des maxima ressemble couramment à ceci :

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Toutes les valeurs se situent autour du nombre 13. Une autre stratégie pour réduire la taille d’un tel tableau consiste à retirer de chaque élément une valeur fixe et à la mémoriser. Nous pouvons par exemple retirer huit :

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Chaque valeur du tableau consomme alors moins de mémoire : dans le premier tableau, nous devons stocker des nombres de 0 à 15, ce qui demande 4 bits, alors que pour le second tableau 3 bits suffisent, car nous ne stockons que des nombres de 0 à 7. Cela suppose évidemment une implémentation du tableau au niveau des bits individuels. Quand nous voudrons lire les valeurs du tableau, nous devrons leur rajouter la valeur mémorisée.

… et un tas d’autres améliorations. La recherche dans ce domaine est toujours en cours, nous pouvons donc certainement nous attendre à d’autres idées intéressantes. La prochaine fois, nous parlerons de la réunion et de l’intersection de vecteurs HyperLogLog et, dans un avenir proche, nous verrons pourquoi il peut être utile de stocker des milliards de vecteurs HyperLogLog.

Liens et sources

• Tu peux consulter toute mon implémentation sur GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – l’article original dans lequel HyperLogLog a été présenté.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – version améliorée du HyperLogLog original, par exemple avec la représentation creuse mentionnée.