Die Serie über Algorithmen zur Schätzung der Anzahl eindeutiger Werte in einer Multimenge wird mit einem Artikel über den State-of-the-Art-Algorithmus HyperLogLog fortgesetzt. Alle Ideen, auf denen dieser Algorithmus beruht, stammen jedoch aus dem zuvor beschriebenen LogLog. Wenn du weiterlesen möchtest, solltest du LogLog daher gut kennen.

Der LogLog-Algorithmus hatte zwei Hauptprobleme:

Ausreißer

Die resultierende Schätzung von LogLog reagiert sehr empfindlich auf Ausreißer, also auf Werte, die sehr weit von den übrigen Werten entfernt sind. Typischerweise sind die maximalen Längen der Nullsuffixe der einzelnen Gruppen ungefähr gleich, liegen zum Beispiel zwischen 12 und 15, aber dann – peng – hat ein Nullsuffix die Länge 27. Dieser große Unterschied bringt die resultierende Schätzung der Anzahl eindeutiger Werte durcheinander, denn mit dem klassischen arithmetischen Mittel kommt man dabei nicht gut zurecht. Im Grunde wirkte dasselbe Prinzip wie bei einigen Top-Managern und Direktoren, die mit ihren hohen Gehältern das Durchschnittsgehalt im Land anheben.

Die Autoren des Algorithmus versuchten das zu lösen, indem sie die Ausreißer loswurden und einige der höchsten Maxima nicht in den Durchschnitt einrechneten, aber das war keine besonders gute Lösung. Später probierten sie ein anderes Vorgehen – statt des arithmetischen Mittels verwendeten sie das harmonische Mittel, das viel bessere Eigenschaften hat, wenn es Werte gibt, die weit vom Durchschnitt entfernt sind.

Sehr schlechte Ergebnisse bei kleinen Kardinalitäten

LogLog liefert schreckliche Ergebnisse, wenn es die Kardinalität kleiner Multimengen schätzen soll. Haben wir in der Multimenge nur wenige eindeutige Elemente, gibt uns LogLog eine unsinnig große Schätzung zurück. Die Autoren haben das raffiniert gelöst – ist die Eingabe eine Multimenge mit niedriger Kardinalität, wird nicht der LogLog-Algorithmus verwendet, sondern ein ganz anderer, nämlich der gute alte Linear Counting. Aber woran erkennen wir, dass die Eingabe eine Multimenge mit kleiner Kardinalität ist, wenn wir die Kardinalität ja gerade nicht kennen?

Wir lassen LogLog die Anzahl der eindeutigen Elemente schätzen, und wenn wir feststellen, dass diese Schätzung relativ niedrig ist, verwerfen wir sie und berechnen sie noch einmal mit dem Linear-Counting-Algorithmus. Erinnern wir uns kurz, wie Linear Counting funktioniert. Am Anfang legen wir ein Bit-Array mit lauter Nullen in einer vorgegebenen Größe an, typischerweise eine Zweierpotenz. Wir gehen alle Elemente der Multimenge durch, berechnen ihren Hash und wandeln ihn in eine ganze Zahl i aus dem Intervall 0 bis Länge des Arrays minus 1 um. An den Index i schreiben wir dann im Array eine Eins. Am Ende zählen wir die Nullen und Einsen im Array und schätzen mithilfe einer einfachen Formel die Kardinalität.

Der LogLog-Algorithmus verwendet aber kein Bit-Array, in dem er die berechneten Hashwerte „speichern“ würde. Stattdessen benutzt er ein Array, in dem er die maximalen Längen der Suffixe aufbewahrt. Das Array kann zum Beispiel so aussehen:

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

wobei jede Zahl die maximale Länge des Nullsuffixes in der jeweiligen Gruppe der berechneten Hashwerte angibt. Ein von null verschiedener Wert an der i-ten Position bedeutet aber zwangsläufig, dass es unter den Werten der Multimenge ein Element gibt, dessen (3-Bit-)Hashwert gleich i ist. Mit anderen Worten: Dieses Array können wir in ein Bit-Array für Linear Counting umwandeln, indem wir die Nullen belassen und jede positive Zahl in eine Eins umwandeln. Aus dem vorherigen Array bekämen wir so das Bit-Array:

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

Jetzt können wir den Linear-Counting-Algorithmus anwenden und mit ihm die Kardinalität schätzen.

Das hat allerdings einen Haken. Wir speichern im Array das maximale Nullsuffix, aber was ist, wenn in einer Gruppe von Werten alle Hashwerte auf eine Eins enden? Verwenden wir zum Beispiel die letzten drei Bits als Kennung der Gruppe, zu der der Hashwert gehört, dann hätte der Hashwert „01001100“ ein Nullsuffix der Länge null – denn der Vektor „01001“ endet auf eine Eins. In das Array der Maxima würden wir somit an den Index 4 (100₂=4₁₀) eine Null schreiben. Bei Linear Counting würde sich das aber so auswirken, dass wir keinen Wert gefunden hätten, dessen Hashwert vier ist, was nicht stimmt.

Deshalb ändern wir den Algorithmus so, dass er ins Array der Maxima nicht die Länge des längsten Nullsuffixes speichert, sondern den Index der „ersten Eins von rechts“ (der Ordnung halber – wir indizieren ab eins), was dasselbe ist, als würden wir zur Länge des Nullsuffixes eins addieren. Dadurch erreichen wir, dass eine Null am Index i bedeutet, dass kein Wert den Hashwert i hat, und ein solches Array können wir dann für Linear Counting verwenden.

Implementierung von HyperLogLog

Schön der Reihe nach:

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

Die Funktion alpha liefert die Korrektur für die berechnete Schätzung, das kennen wir schon vom letzten Mal, nur hat alpha bei HyperLogLog je nach Anzahl der Gruppen einen anderen Wert.

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

Eine Funktion, die die Anzahl der Nullbits am Ende einer Zahl zurückgibt.

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

Eine Funktion, die alle Werte durchgeht, sie in num_buckets Gruppen aufteilt und für jede Gruppe den Index der ersten Eins von rechts berechnet (die Länge des maximalen Nullsuffixes plus eins).

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

Eine leicht angepasste Funktion zur Berechnung des Linear-Counting-Algorithmus.

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

Die Hauptfunktion, die alles zusammenführt. Zuerst berechnet sie die Schätzung mit dem angepassten LogLog, verwendet in der vierten Zeile statt des arithmetischen Mittels das harmonische Mittel und wendet schließlich die Korrektur in Form von Linear Counting an, wenn die berechnete Schätzung kleiner ist als das 2,5-Fache der Gruppenanzahl (in diesem Fall erwarten wir, dass die Standardschätzung von LogLog schlechter wäre als die Verwendung von Linear Counting) und wenn im Array der Maxima mindestens eine Null vorkommt (ein Array, in dem nur Einsen stehen, können wir bei Linear Counting nicht verwenden, siehe vorheriger Artikel). Und wie sind die Ergebnisse von HyperLogLog?

Wir führen einen Testcode aus, der die Kardinalität von Mengen schätzt, die nacheinander die Kardinalität 10, 100, …, 1.000.000 haben:

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)

Ergebnisse:

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

Wir sehen, dass die Ergebnisse immer um weniger als ein Prozent vom richtigen Ergebnis abweichen. Und das ist gut!

Weitere Verbesserungen von HyperLogLog

HyperLogLog hat noch einige weitere interessante Verbesserungen erfahren. Eines der verbleibenden Probleme ist der hohe Speicherbedarf. Das klingt ziemlich merkwürdig, nachdem wir beim letzten Mal den Speicherbedarf in den Himmel gelobt und ausgerechnet haben, dass uns zum Speichern des Arrays der Maxima 768 Bytes genügen. Das Problem entsteht aber, wenn du nicht die Kardinalität einer einzigen riesigen Multimenge berechnen willst, sondern parallel die mehrerer Millionen kleiner Multimengen, oder wenn du diese berechneten Arrays der Maxima in einer Datenbank für spätere Kunststückchen aufbewahren möchtest.

Würden wir zum Beispiel gleichzeitig die Kardinalität von einer Milliarde Multimengen berechnen, bräuchten wir bei der aktuellen Implementierung 1.000.000.000 mal 768 Bytes, also 768 GB. Einerseits ist das nicht schlecht … aber andererseits können wir HyperLogLog besser implementieren.

Dünnbesetzte (sparse) Darstellung

Stellen wir uns vor, wir setzen k=12, verwenden also 12 Bits zur Identifikation der Gruppen und erhalten somit 2¹² verschiedene Gruppen von Hashwerten. Zu Beginn des Algorithmus müssen wir ein Array der Länge 4096 anlegen (siehe Zeile 3 der Funktion count_maxims). Und sagen wir, unsere Multimenge hat drei verschiedene Elemente. Das bedeutet, dass wir im Array an drei verschiedenen Stellen einen Wert setzen und die übrigen 4093 Werte im Array null bleiben – die übrigen 4093 haben wir einfach nicht benutzt. Das ist nicht besonders effizient, oder?

Um zu vermeiden, dass wir ein Array haben, das größtenteils aus ungenutzten Nullen besteht, aber trotzdem wertvollen Speicher belegt, können wir die Werte am Anfang als Paare [index, Wert] speichern. Ein Beispiel zum besseren Verständnis. Dieses Array

[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]

können wir viel speichereffizienter als zwei Paare darstellen:

[0, 7], [4, 12]

Statt einen Haufen ungenutzten Platz im Speicher zu reservieren, können wir nach und nach nur den Platz anlegen, den wir wirklich brauchen. Diese Darstellung nennen wir sparse. Irgendwann wäre diese Darstellung allerdings speicherintensiver als das Speichern in einem Array – dann können wir die sparse Darstellung ohne Informationsverlust in ein klassisches Array umwandeln.

Offsets

Die Praxis hat gezeigt, dass alle Werte im Array ungefähr gleich sind. Das Array der Maxima sieht üblicherweise zum Beispiel so aus:

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

Alle Werte bewegen sich irgendwo um die Zahl 13. Eine weitere Strategie, die Größe eines solchen Arrays zu verringern, besteht darin, von jedem Element einen festen Wert abzuziehen und sich diesen zu merken. Wir können zum Beispiel acht abziehen:

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

Jetzt braucht jeder Wert im Array weniger Speicher – im ersten Array müssen wir Zahlen von 0 bis 15 speichern, wofür wir 4 Bits brauchen, während uns beim zweiten Array 3 Bits genügen, weil wir nur Zahlen von 0 bis 7 speichern. Das setzt natürlich eine Implementierung des Arrays auf der Ebene einzelner Bits voraus. Wenn wir die Werte aus dem Array auslesen wollen, müssen wir den gemerkten Wert wieder zu ihnen addieren.

…und noch ein Haufen weiterer Verbesserungen. Die Forschung auf diesem Gebiet läuft noch, sodass wir uns sicher auf weitere interessante Ideen freuen können. Beim nächsten Mal sprechen wir über die Vereinigung und den Schnitt von HyperLogLog-Vektoren, und irgendwann in naher Zukunft erzählen wir, warum es nützlich sein kann, Milliarden von HyperLogLog-Vektoren zu speichern.

Links und Quellen

• Meine komplette Implementierung kannst du dir auf GitHub ansehen.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] – der Originalartikel, in dem HyperLogLog vorgestellt wurde.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] – eine verbesserte Version des ursprünglichen HyperLogLog, zum Beispiel um die erwähnte sparse Darstellung.