LogLog: So schätzt du die Anzahl eindeutiger Werte
Nach den vorherigen Teilen über Linear Counting und Min Value kommen wir endlich zu fast dem allerbesten probabilistischen Algorithmus zur Schätzung der Anzahl eindeutiger Werte in einem Datensatz: LogLog. Besser ist nur noch sein kleiner Bruder HyperLogLog, der auf LogLog aufbaut, aber von dem erzählen wir erst beim nächsten Mal.
Wiederholen wir die Aufgabenstellung. Als Eingabe haben wir einen Datensatz bzw. eine Multimenge, zum Beispiel ein Array oder einen Generator von IDs. In diesem Array stehen manche Werte mehrfach und wir wollen die Anzahl der eindeutigen Werte in diesem Array berechnen. Diese Anzahl nennen wir Kardinalität. Wir erwarten, dass diese Kardinalität wirklich groß ist, sonst können wir herkömmliche Algorithmen verwenden.
Die Idee des LogLog-Algorithmus
Stellen wir uns vor, wir haben eine Menge von Binärvektoren. Keine Angst, zum Beispiel ist 0001011001001100 ein Binärvektor der Länge 16. Nehmen wir an, wir haben Binärvektoren der Länge 32 und insgesamt eine Million davon, alle völlig zufällig erzeugt. Wie viele Vektoren enden auf die Ziffer null?
Das können wir natürlich nicht genau wissen, aber wenn wir die Vektoren wirklich zufällig erzeugt haben, sollte ungefähr die Hälfte davon auf null enden, also 500 Tausend. Wie viele Vektoren enden auf 00? Ein Viertel. Auf 000? Ein Achtel. Und so weiter. Das können wir ungefähr so darstellen:
Vektormuster Anteil an allen Vektoren
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Fragen wir nach einem Suffix (ein Suffix ist eine Zeichenkette, auf die eine andere Zeichenkette endet – das Gegenteil eines Präfixes) der Länge d, erwarten wir, v Vektoren zu finden, die auf dieses Suffix enden. Den Wert v berechnen wir als:
wobei N die Anzahl aller Vektoren im Datensatz ist. Ein Suffix der Länge 3 (zum Beispiel …010) sollte in 1/2^3 N = 1/8 N der Vektoren vorkommen, also in 12,5 % aller Vektoren.
Jetzt machen wir einen kleinen Mindfuck. Nehmen wir eine Multimenge aus 1024 eindeutigen Vektoren. Wie viele Vektoren sollten auf das Suffix 0000000000 enden? (zehn Nullen) Wir setzen in die Formel ein und erhalten
Huh, einen! Unter tausend zufällig erzeugten Binärvektoren sollte genau ein Vektor sein, der auf zehn Nullen endet. Und wie nutzen wir diese Information, um die Anzahl der eindeutigen Elemente zu schätzen? Wir können nämlich auch umgekehrt vorgehen. Was, wenn wir alle Binärvektoren der Eingabe durchgehen und feststellen, dass es im Datensatz genau einen Vektor gibt, der auf zehn Nullen endet? Dann können wir doch schätzen, dass im Datensatz 1024 Vektoren waren!
Wir verallgemeinern und bauen den Algorithmus zusammen
Das Ziel sollte sein, ein Suffix zu finden, das nur in einem einzigen Vektor enthalten ist, wobei dieses Suffix möglichst kurz ist. Das geht allerdings nur sehr schwer, denn um wirklich so einen Vektor zu finden, müssten wir alle Suffixe speichern, was wir nicht wollen, weil es viel zu viel Speicher brauchen würde. Stattdessen geben wir uns damit zufrieden, die längste Folge von Nullen am Ende eines Vektors zu suchen.
Wir gehen also alle Vektoren durch, bei jedem Vektor zählen wir, wie viele Nullen er am Ende hat, und in einer Variablen merken wir uns das Maximum dieser Werte. Wenn wir alle Vektoren durchlaufen haben, kennen wir die Länge des längsten Suffixes, das nur aus Nullen besteht. Diese Länge bezeichnen wir mit dem Buchstaben d. Nun formen wir die vorherige Formel so um, dass wir die Variable N isolieren, damit sie die Ausgabe des Algorithmus ist und nicht die Eingabe. Dabei können wir statt v eins einsetzen, weil wir erwarten, genau einen solchen Vektor zu finden, also erwarten wir v=1.
Finden wir also die Länge d des längsten Nullsuffixes, schätzen wir die Kardinalität mit der Formel N=2d.
Wie bekommen wir zufällige Binärvektoren?
Mit zufälligen Binärvektoren funktioniert der Algorithmus schon, aber wie wenden wir dieses Vorgehen auf reale Daten an? Wie üblich verwenden wir auch hier eine geeignete Hashfunktion. Haben wir als Eingabe einen Datensatz, zum Beispiel IDs (Strings), hashen wir sie zuerst. Die Ausgabe einer n-Bit-Hashfunktion sind n Bits, die praktisch wie zufällig erzeugte Binärvektoren aussehen.
Jetzt können wir unseren Algorithmus aufschreiben:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
Die Funktion trailing_zeroes liefert die Anzahl der Nullen am Ende einer Zahl. Wie sie das macht? Wenn du es nicht aus dem Code verstanden hast, frag lieber gar nicht erst. Und wie gut ist die Funktion? Für eine Menge mit hunderttausend eindeutigen Elementen lieferte die Funktion die Schätzung 524.288.
Naja…
Das ist nicht so richtig gut, oder? Aber das macht nichts! Wir versuchen, den Algorithmus genau wie beim vorherigen Min Value zu verbessern. Wir teilen die Eingabedaten in mehrere disjunkte Gruppen auf, berechnen für jede Gruppe das maximale Nullsuffix, berechnen am Ende die durchschnittliche Länge des Nullsuffixes und verwenden diese für die Schätzung der Anzahl der eindeutigen Werte.
Wir können zum Beispiel festlegen, dass die letzten zwei Bits jedes Vektors die Nummer der Gruppe bestimmen, zu der der Vektor gehört. Diese sechs Vektoren
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
können wir je nach Endung in vier Gruppen aufteilen:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Als Nächstes berechnen wir die Länge des längsten Nullsuffixes in jedem Vektor, wobei wir aber die Bits überspringen, die wir als Gruppennummer verwendet haben. Die Nullsuffixe markieren wir grün:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Am Ende stehen dort die Längen der längsten Nullsuffixe der jeweiligen Gruppe. Aus diesen Längen können wir das arithmetische Mittel berechnen, das 2,75 ergibt. Den Wert setzen wir in die Formel ein und erhalten
Wir erhalten die durchschnittliche Anzahl der eindeutigen Elemente in jeder Gruppe. Das stimmt natürlich überhaupt nicht, aber darüber machen wir uns keine Sorgen, für kleine Mengen liefert der LogLog-Algorithmus schreckliche Ergebnisse.
Um die Kardinalität der gesamten Menge zu schätzen, müssen wir diesen Wert noch mit der Anzahl der Gruppen multiplizieren: 6,727 · 4 = 26,908. Der Algorithmus hat berechnet, dass im Datensatz ungefähr 27 eindeutige Werte sind. Es waren sechs, also liegt er völlig daneben, aber das macht jetzt wirklich nichts.
Implementierung des Algorithmus
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
Der Parameter k bestimmt, wie viele Bits als Gruppenindex genommen werden. Dieser Parameter bestimmt die Genauigkeit des Algorithmus – je höher k, desto größer die Genauigkeit. In der Variablen bucket_index steht die Nummer der Gruppe. Wie funktioniert die Magie rechts vom Gleichheitszeichen?
In der Variablen num_buckets steht die Anzahl der Gruppen, die immer eine Potenz von zwei ist. Ist zum Beispiel k = 3, dann ist num_buckets=8. Die Zahl 8 hat im Dualsystem die Form 1000. Ziehen wir eins ab, erhalten wir die Zahl 7 mit der Form 0111. Zieht man von num_buckets eins ab, erhält man immer eine Zahl, die am Ende k Einsen und davor lauter Nullen hat. Dann führen wir ein bitweises UND durch (das ist der Operator &). Für den Vektor 1110110010100101 würde diese Operation so aussehen:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Der Zweck dieser ganzen Magie ist, dass wir eine Zahl erhalten, die am Anfang lauter Nullen enthält und deren letzte k Bits mit denen des gegebenen Hashs h übereinstimmen.
Als Nächstes berechnen wir bucket_hash, also den ursprünglichen Hash, aus dem wir die letzten k Bits entfernen, indem wir den ganzen Hash um k Bits nach rechts verschieben. Die Verschiebung verhält sich so, dass sie einfach alle Bits der Zahl um k Bits nach rechts schiebt und die Zahl von links mit Nullen auffüllt. (Eine Verschiebung nach rechts um eins verhält sich genauso, als würdest du die Zahl durch zwei teilen und den Rest verwerfen.) Aus dem Vektor 1110110010100101 würden wir nach der Verschiebung um drei 0001110110010100 erhalten. Dieser Vektor würde in der Variablen bucket_hash gespeichert.
Als Nächstes berechnen wir die Anzahl der Nullen am Ende dieses Vektors, und wenn dieser Wert größer ist als das aktuelle Maximum, das im Array max_zeroes am Index bucket_index gespeichert ist, überschreiben wir den Wert.
Am Ende berechnen wir nur noch die durchschnittliche Anzahl der Nullen in allen Gruppen und daraus, wie viele eindeutige Elemente es im Durchschnitt in jeder Gruppe gibt (2 ** average_max_zeros). Da wir insgesamt num_buckets Gruppen haben, multiplizieren wir diesen Wert mit der Anzahl der Gruppen und erhalten so die endgültige Schätzung der Anzahl eindeutiger Elemente. Uff, und es hat nicht einmal wehgetan. Die Ergebnisse für mehrere Datensätze mit 250.000 eindeutigen Werten und k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neeein, immer noch schlecht :-(. Aber wir sind schon ziemlich nah dran, keine Sorge. Beachte, dass alle Ergebnisse größer sind als das richtige Ergebnis. Im Laufe des Algorithmus sammeln sich nämlich verschiedene Fehler an, und die Schätzung ist deshalb merklich größer als das richtige Ergebnis. Diese Fehler sind aber ziemlich konstant und man kann abschätzen, wie groß der Fehler war. Multiplizieren wir die Schätzung mit der Hausnummer 0.79402, erhalten wir deutlich bessere Ergebnisse:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Ich habe noch eine Multimenge mit der Kardinalität eine Million ausprobiert, die Ergebnisse:
Ergebnis Fehler
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Schön! Der Fehler liegt unter 2,5 %, was eine ordentliche Leistung ist. Und das ist, meine Damen und Herren, der Algorithmus LogLog. Die endgültige Implementierung samt Hausnummer sieht so aus:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Wie wir diesen Algorithmus anpassen, um den sagenhaften und allerbesten HyperLogLog zu erhalten, erzählen wir beim nächsten Mal. Vorerst schauen wir uns an, wie speicherintensiv der Algorithmus ist.
Speicherbedarf
Der Algorithmus ist hinsichtlich des belegten Speichers sehr effizient. Das Einzige, was wir uns merken müssen, ist das Array, das die Maxima hält. Die Länge dieses Arrays wird vom Wert k bestimmt, also von der Anzahl der Bits des Vektors, die wir als Gruppenindex nehmen. Für ein gegebenes k haben wir insgesamt 2k verschiedene Gruppen, und das Array der Maxima hat deshalb die Länge 2k. Diesen Wert haben wir in der Implementierung num_buckets genannt.
Wie groß muss eine Zelle des Arrays sein? Wir speichern darin die Längen der Nullsuffixe. Ich kann dir vorab verraten, dass eine 64-Bit-Hashfunktion wahrscheinlich für alle denkbaren Multimengen der Welt ausreicht, also müssen wir in diesem Array Zahlen von 0 (ein Vektor aus lauter Einsen) bis 64 (ein Vektor aus lauter Nullen) speichern können. Nehmen wir weiter an, dass k immer größer als null ist, dann genügt es, Zahlen von 0 bis 63 zu speichern. Dafür reichen uns, bitte schön, 6 Bits, denn 26 = 64.
Ja, uns genügt ein „Array“, in dem eine Zelle 6 Bits groß ist. Weiter kann ich dir verraten, dass der Wert k=10 genügt, um die Kardinalität bis in die Hunderte von Millionen ganz ordentlich zu schätzen. So eingestellt würde der Algorithmus ein Array der Größe 210 = 1024 anlegen, in dem jede Zelle 6 Bits belegt. Insgesamt würde dieses Array 6144 Bits belegen, das sind 768 Byte. Nicht einmal ein Kilobyte.
Und das ist alles.
Mehr müssen wir nicht speichern, die berechneten Hashes können wir sofort wieder verwerfen, es genügt uns, die Anzahl der Nullen am Ende des Vektors zu kennen.
Beachte, dass sich der Speicherbedarf nicht stark ändern würde, wenn du eine größere Hashfunktion verwendest, die zum Beispiel 128 Bits liefert. Wir müssten nämlich Zahlen von 0 bis 127 speichern, wofür uns 7 Bits genügen. Den Speicherbedarf bestimmt also vor allem der Parameter k, also die Anzahl der Gruppen.
LogLog eignet sich vor allem dort, wo wir Multimengen mit wirklich großer Kardinalität zählen müssen. Wie schon das einfache Beispiel oben gezeigt hat, kommt LogLog mit Multimengen, die eine kleine Kardinalität haben, nicht ganz ideal zurecht. Dem kann man aber ebenfalls abhelfen, zum Beispiel, indem wir für die Schätzung einen anderen Algorithmus verwenden, sobald wir feststellen, dass die Multimenge eine niedrige Kardinalität hat, etwa das bereits beschriebene Linear Counting. Auch davon wird beim nächsten Mal die Rede sein.
Quellen:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (daraus ist der LogLog-Code mehr oder weniger abgeschrieben)
Kapitel: Linear Counting: Wie man die Anzahl eindeutiger Werte schätzt, Min Value: So schätzt du die Anzahl eindeutiger Werte, LogLog: So schätzt du die Anzahl eindeutiger Werte, HyperLogLog: Wie man die Anzahl eindeutiger Werte sehr genau schätzt
