Die Serie über Algorithmen zur Schätzung der Anzahl der eindeutigen Werte in einer Menge wird mit einem Artikel über den aktuellen Algorithmus HyperLogLog fortgesetzt. Alle Ideen, die diesem Algorithmus zugrunde liegen, basieren jedoch auf dem zuvor beschriebenen LogLog-Algorithmus; wenn Sie also weiterlesen möchten, sollten Sie LogLog gut kennen.

Der LogLog-Algorithmus hatte zwei Hauptprobleme:

Ausreißer

Die resultierende LogLog-Schätzung ist sehr anfällig für Ausreißer, d. h. Werte, die sehr weit von den anderen Werten entfernt sind. Das liegt daran, dass die meisten maximalen Längen der Null-Präfixe für jede Gruppe ungefähr gleich sind, z. B. zwischen 12 und 15, aber dann - bumm - hat ein Null-Suffix eine Länge von 27. Dieser große Unterschied bringt die resultierende Schätzung der Anzahl der Unikate durcheinander, da der klassische arithmetische Durchschnitt damit nicht gut umgehen kann. Im Grunde hat das gleiche Prinzip funktioniert, wie wenn einige Topmanager und Direktoren mit ihren hohen Gehältern den Durchschnittslohn im Land anheben.

Die Autoren des Algorithmus versuchten, dies in den Griff zu bekommen, indem sie die Ausreißer beseitigten und die wenigen höchsten Spitzenwerte nicht in den Durchschnitt aufnahmen, aber das war keine sehr gute Lösung. Später versuchten sie es mit einem anderen Ansatz - statt des arithmetischen Mittels verwendeten sie das harmonische Mittel, das bei Werten, die weit vom Mittelwert entfernt sind, viel bessere Eigenschaften aufweist.

Sehr schlechte Ergebnisse bei kleinen Kardinalitäten

LogLog erzielt schlechte Ergebnisse, wenn es die Kardinalität von kleinen Multiplizitäten schätzen muss. Wenn es nur wenige eindeutige Elemente in einer Menge gibt, liefert LogLog eine unsinnig große Schätzung. Die Autoren haben dieses Problem auf originelle Weise gelöst: Wenn wir eine Multimenge mit geringer Kardinalität als Eingabe haben, verwenden wir nicht LogLog, sondern einen völlig anderen Algorithmus, nämlich die altbekannte lineare Zählung. Nun, ja, aber woher wissen wir, dass wir eine Multimenge mit geringer Kardinalität als Eingabe haben, wenn wir die Kardinalität 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 die Schätzung und berechnen sie mit dem Algorithmus der linearen Zählung neu. Erinnern wir uns kurz daran, wie die lineare Zählung funktioniert. Wir beginnen mit der Zuweisung eines Null-(Bit-)Arrays einer bestimmten Größe, in der Regel eine Potenz von zwei. Wir durchlaufen alle Elemente des Multisets, berechnen ihren Hash und wandeln ihn in eine ganze Zahl i aus dem Intervall 0 bis zur Länge des Arrays minus 1 um. Dann speichern wir eine Eins am Index des i im Array. Schließlich zählen wir die Anzahl der Nullen und Einsen im Array und verwenden eine einfache Formel, um die Kardinalität zu schätzen.

Der LogLog-Algorithmus verwendet jedoch kein Bit-Array zum "Speichern" der berechneten Hashes. Stattdessen verwendet er ein Array, in dem er die maximalen Suffixlängen speichert. Das Array könnte zum Beispiel so aussehen:

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

wobei jede Zahl die maximale Länge des Null-Suffixes in dieser Gruppe von berechneten Hashes angibt. Ein Wert ungleich Null an der i-ten Position bedeutet dann jedoch zwangsläufig, dass es unter den Werten in der Multimenge ein Element gibt, dessen (Drei-Bit-)Hash gleich i ist. Mit anderen Worten, wir können diese Matrix in eine Bitmatrix für lineares Zählen umwandeln, indem wir die Nullen beibehalten und jede positive Zahl in eine Eins umwandeln. So erhalten wir ein Bit-Array aus dem vorherigen Array:

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

Jetzt können wir den linearen Zählalgorithmus anwenden und damit die Kardinalität schätzen.

Allerdings gibt es einen Haken. Wir speichern das maximale Nullsuffix im Array, aber was ist, wenn alle Hashes in einer Wertemenge auf eins enden? Wenn wir z. B. die letzten drei Bits als Kennung der Gruppe verwenden, zu der der Hash gehört, dann wäre die Länge des Nullsuffixes dieses Hashes "01001100" gleich Null - weil der Vektor "01001" auf Eins endet. Wir würden also eine Null in das Maxima-Array bei Index 4 _(1002=410) speichern. In einem linearen Zählalgorithmus würde dies jedoch zeigen, dass wir keinen Wert gefunden haben, der eine Vier nach der Raute hat, was nicht stimmt.

Daher ändern wir den Algorithmus so ab, dass er nicht die Länge der längsten Nullsuffixe im Feld max speichert, sondern den Index der "ersten von rechts" (der Klarheit halber gehen wir von 1 aus), was dasselbe ist wie das Hinzufügen von 1 zur Länge des Nullsuffixes. Dies bedeutet, dass eine Null bei Index i bedeutet, dass kein Wert einen Hash gleich i hat, und wir können dann ein solches Array für die lineare Zählung verwenden.

Implementierung von HyperLogLog

Ein Schritt nach dem anderen:

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

Die alpha-Funktion gibt eine Korrektur für die berechnete Schätzung zurück, wir kennen das schon vom letzten Mal, nur in der HyperLogLog-Option hat alpha einen anderen Wert, abhängig von der Anzahl der Gruppen.

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(wert) 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 den Index des ersten Wertes von rechts (die Länge des maximalen Nullen-Suffixes plus eins) für jede Gruppe berechnet.

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

Leicht modifizierte Funktion zur Berechnung des linearen Zählalgorithmus.

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) und (number_of_ones < num_buckets): return linear_counting(number_of_ones, num_buckets) else: return estimate

Die Hauptfunktion, die alles zusammenfasst. Sie berechnet zunächst eine Schätzung unter Verwendung des modifizierten LogLog, verwendet in der vierten Zeile das harmonische Mittel anstelle des arithmetischen Mittels und wendet schließlich eine Korrektur in Form von Linear Counting an, wenn die berechnete Schätzung weniger als das 2,5-fache der Anzahl der Gruppen beträgt (an diesem Punkt erwarten wir, dass die Standard-LogLog-Schätzung schlechter ist als bei Verwendung von Linear Counting) und wenn mindestens eine Null im Maxima-Feld steht (wir können bei Linear Counting kein Feld verwenden, das nur Einsen enthält, siehe vorheriger Artikel). Und was 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:

Kardinalität: 10.0030530001, relativer Fehler: 0.999694793165 Kardinalität: 100.306423257, relativer Fehler: 0.996945128268 Kardinalität: 1003.0892434, relativer Fehler: 0.99692027063 Kardinalität: 10013.1348931, relativer Fehler: 0.998688233677 Kardinalität: 100520.045562, relativer Fehler: 0.994826449206 Kardinalität: 998088.420332, relativer Fehler: 1.0019152408

Wie wir sehen, weichen die Ergebnisse immer um weniger als ein Prozent vom richtigen Ergebnis ab. Und das ist gut so!

Andere Verbesserungen an HyperLogLog

HyperLogLog hat einige weitere interessante Verbesserungen erfahren. Eines der verbleibenden Probleme ist der hohe Speicherbedarf. Das klingt etwas seltsam, denn beim letzten Mal haben wir den Speicherverbrauch in den Himmel gelobt und errechnet, dass wir nur 768 Bytes benötigen, um ein Array von Maximalwerten zu speichern. Problematisch wird es erst, wenn man die Kardinalität nicht nur einer großen, sondern mehrerer Millionen kleiner Multisets parallel berechnen will, oder wenn man diese berechneten Arrays von Maxima in einer Datenbank für ein späteres Schachmachra speichern will.

Wenn wir zum Beispiel die Kardinalität von einer Milliarde Multisets gleichzeitig berechnen würden, bräuchten wir 1.000.000 mal 768 Bytes, was in der aktuellen Implementierung 768 GB entspricht. Einerseits ist das nicht schlecht ... aber andererseits können wir HyperLogLog besser implementieren.

Spärliche Darstellung

Stellen wir uns vor, wir setzen k=12, d.h. wir verwenden 12 Bits, um die Gruppen zu identifizieren und erhalten so²¹² verschiedene Hash-Gruppen. Zu Beginn des Algorithmus müssen wir ein Array der Länge 4096 zuweisen (siehe Zeile 3 der Funktion count_maxims). Und nehmen wir an, dass unser Multiset drei verschiedene Elemente hat. Das bedeutet, dass wir einen Wert an drei verschiedenen Stellen im Array setzen, und die restlichen 4093 Werte im Array bleiben null; wir haben die restlichen 4093 einfach nicht verwendet. Das ist nicht sehr effizient, oder?

Um ein Array zu vermeiden, das größtenteils aus Nullen besteht und unbenutzt ist, aber trotzdem einen wertvollen Teil des Speichers beansprucht, können wir die Werte als [index, value]-Paare am Anfang speichern. 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]

kann viel speichereffizienter als zwei Paare dargestellt werden:

[0, 7], [4, 12]

Anstatt einen Haufen ungenutzten Speicherplatz zuzuweisen, können wir schrittweise nur den Platz zuweisen, den wir wirklich brauchen. Wir nennen diese Darstellung spärlich. Irgendwann wäre eine solche Darstellung jedoch speicherintensiver als die Speicherung in einem Array - dann können wir die spärliche Darstellung ohne Informationsverlust in ein klassisches Array übertragen.

Offsets

Die Praxis hat gezeigt, dass alle Werte in einem Array ungefähr gleich sind. Ein Array von Maxima sieht zum Beispiel normalerweise so aus:

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

Alle Werte liegen irgendwo um die Zahl 13 herum. Eine andere Strategie zur Verringerung der Größe eines solchen Arrays besteht darin, von jedem Element einen festen Wert abzuziehen und sich diesen Wert zu merken. Wir können zum Beispiel eine 8 subtrahieren:

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

An diesem Punkt verbraucht jeder Wert im Array weniger Speicherplatz - im ersten Array müssen wir Zahlen von 0 bis 15 speichern, wofür wir 4 Bits benötigen, während wir für das zweite Array nur 3 Bits benötigen, weil wir Zahlen von 0 bis 7 speichern. Dies setzt natürlich eine Array-Implementierung auf Bit-Ebene voraus. In dem Moment, in dem wir die Werte aus dem Array lesen wollen, müssen wir den notierten Wert wieder dazu addieren.

eine Reihe weiterer Verbesserungen. Die Forschung in diesem Bereich ist noch nicht abgeschlossen, so dass wir uns sicherlich auf weitere interessante Ideen freuen können. Nächstes Mal werden wir über die Vereinheitlichung und Kreuzung von HyperLogLog-Vektoren sprechen, und irgendwann in naher Zukunft werden wir erörtern, warum die Speicherung von Milliarden von HyperLogLog-Vektoren nützlich sein könnte.

Links und Ressourcen

• Sie können meine gesamte Implementierung auf GitHub sehen.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] - das Originalpapier zur Einführung von HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm [ PDF] - Eine verbesserte Version des ursprünglichen HyperLogLog, zum Beispiel durch Hinzufügen der oben erwähnten spärlichen Darstellung.