✖

LogLog: Wie man die Anzahl der eindeutigen Werte schätzt

Kapitoly: Lineare Zählung: Wie man die Anzahl der eindeutigen Werte schätzt, Minimalwert: Wie man die Anzahl der eindeutigen Werte schätzt, LogLog: Wie man die Anzahl der eindeutigen Werte schätzt, HyperLogLog: Wie man die Anzahl der eindeutigen Werte schätzt

Nach den vorangegangenen Beiträgen über lineares Zählen und Minimalwert kommen wir nun endlich zu dem fast besten probabilistischen Algorithmus zur Schätzung der Anzahl eindeutiger Werte in einem Datensatz, LogLog. Das Einzige, was noch besser ist, ist sein kleiner Bruder HyperLogLog, der auf LogLog basiert, aber dazu mehr beim nächsten Mal.

Wiederholen wir die Problemstellung. Als Eingabe haben wir einen Datensatz/Multiset, z.B. ein Array/Generator von IDs. Es gibt mehrere Werte in diesem Feld und wir wollen die Anzahl der eindeutigen Werte in diesem Feld zählen. Wir nennen diese Zahl die Kardinalität. Wir gehen davon aus, dass diese Kardinalität sehr groß ist, andernfalls können wir herkömmliche Algorithmen verwenden.

Die Idee hinter dem LogLog-Algorithmus

Stellen Sie sich vor, wir haben eine Menge binärer Vektoren. Seien Sie nicht erschrocken, zum Beispiel ist diese 0001011001001100 ein binärer Vektor der Länge 16. Nehmen wir an, wir haben binäre Vektoren der Länge 32 und insgesamt eine Million davon, die alle völlig zufällig erzeugt wurden. Wie viele Vektoren enden mit Null?

Das können wir natürlich nicht genau wissen, aber wenn wir die Vektoren wirklich zufällig erzeugt haben, sollte etwa die Hälfte von ihnen auf Null enden, also 500.000. Wie viele Vektoren enden mit 00? Ein Viertel. 000? Acht. Und so weiter. Wir können das ungefähr so darstellen:

Vektormuster Anteil an allen Vektoren ...xxxxxx0 50% ...xxxxx00 25% ...xxxx000 12,5% ...xxx0000 6,25% ... ...

Wenn wir nach einem Suffix (ein Suffix ist eine Zeichenkette, die eine andere Zeichenkette abschließt - das Gegenteil eines Präfixes) der Länge d fragen, erwarten wir, dass wir Vektoren finden, die mit diesem Suffix enden. Wir berechnen den Wert von v als:

$$\Large v=\frac{1}{2^d}\cdot N$$

wobei N die Anzahl aller Vektoren in der Menge ist. Ein Suffix der Länge 3 (z. B. ...010) sollte in 1/2^3 N = 1/8 N Vektoren vorkommen, d. h. in 12,5 % aller Vektoren.

Jetzt machen wir einen kleinen Mindfuck. Nehmen wir an, wir haben eine Menge von 1024 eindeutigen Vektoren. Wie viele Vektoren sollten mit dem Suffix 0000000000 enden?

$$v=\frac{1}{2^{10}}\cdot1024=\frac{1}{1024}\cdot1024=1$$

Hm, einer! In tausend zufällig erzeugten binären Vektoren sollte es genau einen Vektor geben, der mit zehn Nullen endet. Und wie können wir diese Information nutzen, um die Anzahl der eindeutigen Elemente zu schätzen? Weil wir das Gegenteil tun können. Was wäre, wenn wir alle binären Vektoren in der Eingabe durchgehen und feststellen, dass es einen einzigen Vektor in der Menge gibt, der mit zehn Nullen endet? Dann können wir schätzen, dass es 1024 Vektoren in der Menge gab!

Wir verallgemeinern und konstruieren einen Algorithmus

Das Ziel sollte sein, ein Suffix zu finden, das nur in einem einzigen Vektor enthalten ist, und dieses Suffix ist so kurz wie möglich. Das ist jedoch sehr schwierig, denn um einen solchen Vektor zu finden, müssten wir alle Suffixe speichern, was wir nicht tun wollen, weil es zu viel Speicherplatz beanspruchen würde. Stattdessen begnügen wir uns mit der Suche nach der längsten Folge von Nullen am Ende des Vektors.

Wir gehen also alle Vektoren durch, zählen für jeden Vektor, wie viele Nullen er am Ende enthält, und speichern das Maximum dieser Werte in einer Variablen. Wenn wir alle Vektoren durchgegangen sind, kennen wir die Länge des längsten Suffixes, das ausschließlich aus Nullen besteht. Wir bezeichnen diese Länge mit d. Wir ändern nun die vorherige Formel, um die Variable N zu isolieren, d. h. sie zur Ausgabe des Algorithmus zu machen, nicht zur Eingabe. Dabei können wir eins anstelle von v einsetzen, weil wir erwarten, nur einen solchen Vektor zu finden, d. h. wir erwarten, dass v=1 gilt.

$$\begin{eqnarray} v&=&\frac{N}{2^d}\\ v\cdot2^d&=&N\\ 2^d&=&N \end{eqnarray}$$

Wenn wir also die Länge d des längsten Null-Suffixes finden, können wir die Kardinalität mit der Formel N=2d schätzen.

Wie erhält man zufällige binäre Vektoren?

Der Algorithmus funktioniert bereits mit zufälligen binären Vektoren, aber wie wenden wir ihn auf reale Daten an? Wie üblich verwenden wir eine geeignete Hash-Funktion. Wenn wir eine Reihe von Daten als Eingabe haben, z. B. IDs (Zeichenketten), hacken wir sie zuerst. Die Ausgabe der n-Bit-Hash-Funktion sind n Bits, die aus praktischer Sicht wie zufällig erzeugte binäre Vektoren aussehen.

An dieser Stelle können wir unseren Algorithmus schreiben:

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(zeros_length, max_zero_suffix_length) return 2 ** max_zero_suffix_length

Die Funktion trailing_zeroes gibt die Anzahl der Nullen am Ende einer Zahl zurück. Wie macht sie das? Wenn Sie es nicht aus dem Code herausbekommen haben, fragen Sie gar nicht erst. Und wie hoch ist die Erfolgsquote der Funktion? Für eine Menge mit 100.000 eindeutigen Elementen lieferte die Funktion einen Schätzwert von 524.288.

Nun ja...

Das ist nicht gerade gut, oder? Aber das ist in Ordnung! Versuchen wir, den Algorithmus auf die gleiche Weise zu verbessern wie den vorherigen Min-Wert. Wir teilen die Eingabedaten in mehrere disjunkte Gruppen auf und berechnen das maximale Nullsuffix für jede Gruppe, und schließlich berechnen wir die durchschnittliche Länge des Nullsuffixes und verwenden diese, um die Anzahl der Unikate zu schätzen.

So können wir beispielsweise sagen, dass die letzten beiden Bits eines jeden Vektors die Nummer der Gruppe bestimmen, zu der der Vektor gehört. Die sechs Vektoren

1101110111111011 1110110010100101 1011001111110010 1111101100000011 1010101000100000 0110010110011000

können anhand ihrer Endungen in vier Gruppen unterteilt werden:

00011010101000100000 1110110010100101011001011001100010111011001111110010 1101110111111011 1111101100000011

Als Nächstes berechnen wir die Länge des längsten Null-Suffixes in jedem Vektor, lassen aber die Bits aus, die wir als Gruppennummer verwendet haben. Wir markieren die Null-"Suffixe" in grün:

00 011010101000100000 1110110010100101 011001011001100010111011001111110010 1101110111111011111110110000001100:3 01: 0 10: 2 11: 6

Am Ende stehen die längsten Nullsuffixe aus dieser Gruppe. Aus diesen Suffixen können wir das arithmetische Mittel berechnen, das 2,75 beträgt. Wir setzen diesen Wert in die Formel ein, und es ergibt sich

$$2^{2{,}75}\approx6{,}727$$

Wir erhalten die durchschnittliche Anzahl der eindeutigen Elemente in jeder Gruppe. Das passt natürlich überhaupt nicht, aber machen wir uns nichts draus, bei kleinen 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 errechnet, dass es ungefähr 27 eindeutige Werte in der Menge gibt. Es waren sechs, also liegt er völlig daneben, aber das spielt jetzt keine Rolle.

Die 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 verwendet werden. Dieser Parameter bestimmt die Genauigkeit des Algorithmus - je höher k, desto höher die Genauigkeit. Die Variable bucket_index speichert die Gruppennummer. Wie funktioniert die Magie auf der rechten Seite der Gleichung?

Die Variable num_buckets enthält die Anzahl der Gruppen, die immer eine Potenz von zwei ist. Wenn z. B. k = 3 ist, dann ist num_buckets = 8. Die Zahl 8 hat im Binärsystem die Form 1000. Zieht man eine ab, erhält man die Zahl 7, die die Form 0111 hat. Wenn man von num_buckets eine subtrahiert, erhält man immer eine Zahl, die am Ende k Einsen und davor alle Nullen hat. Als Nächstes führen wir das logische Produkt durch (das ist der Operator &). Für den Vektor 1110110010100101 würde diese Operation wie folgt aussehen:

 1110110010100101 & 0000000000000111 ------------------ 0000000000000101

Der Zweck dieser ganzen Zauberei ist es, eine Zahl zu erhalten, die am Anfang alle Nullen enthält und deren letzte k Bits mit dem gegebenen Hash h übereinstimmen.

Als Nächstes berechnen wir bucket_hash, d.h. den ursprünglichen Hash, aus dem wir die letzten k Bits entfernen, indem wir den gesamten Hash um k Bits nach rechts verschieben. Bei der Verschiebung werden einfach alle Bits der Zahl k Bits nach rechts verschoben und die Zahl mit Nullen von links aufgefüllt (eine Bitverschiebung um eins nach rechts verhält sich genauso, als würde man 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 werden.

Als Nächstes zählen wir die Anzahl der Nullen am Ende dieses Vektors, und wenn dieser Wert größer ist als der aktuelle Maximalwert, der im Feld max_zeroes im bucket_index gespeichert ist, überschreiben wir den Wert.

Am Ende zählen wir einfach die durchschnittliche Anzahl der Nullen in allen Gruppen und berechnen die durchschnittliche Anzahl der eindeutigen Elemente in jeder Gruppe(2 ** average_max_zeros). Da wir insgesamt num_buckets Gruppen haben, multiplizieren wir diesen Wert mit der Anzahl der Gruppen, um eine endgültige Schätzung der Anzahl der eindeutigen Elemente zu erhalten. Igitt, und das hat auch nicht geschadet. Ergebnisse für mehrere Datensätze mit 250.000 eindeutigen Elementen und k=10:

331774.56203 323349.39265 307343.444439 309430.914045 294512.379123

Nee, immer noch falsch :-(. Aber wir sind ziemlich nah dran, keine Sorge. Beachten Sie, dass alle Ergebnisse größer sind als das richtige Ergebnis. Das liegt daran, dass sich während des Algorithmus verschiedene Fehler ansammeln und die Schätzung daher deutlich größer ist als das richtige Ergebnis. Diese Fehler sind jedoch ziemlich konstant und es ist möglich abzuschätzen, wie groß der Fehler war. Wenn wir die Schätzung mit der Hausnummer 0,79402 multiplizieren, erhalten wir wesentlich bessere Ergebnisse:

263435.63774306054 256745.88475195298 244036.84175345476 245694.33437001088 233848.71927124445

Ich habe es mit einem anderen Multiset versucht, das eine Kardinalität von einer Million hat, mit folgenden Ergebnissen:

Ergebnis Fehler 1017297.17411 1.01729717411 1022820.99717 1.02282099717 984108.725487 0.984108725487 1018675.32683 1.01867532683 1007020.2853 1.0070202853

Schön und gut! Der Fehler liegt unter 2 %, was eine ordentliche Leistung ist. Und das, meine Damen und Herren, ist der LogLog-Algorithmus. Die endgültige Implementierung mit der Hausnummer sieht wie folgt 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(wert) 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 man diesen Algorithmus modifizieren kann, um das mythische und beste HyperLogLog zu erhalten, werden wir beim nächsten Mal erzählen. Schauen wir uns erst einmal an, wie speicherintensiv der Algorithmus ist.

Speicherbedarf

Der Algorithmus ist sehr speichereffizient. Das Einzige, was wir uns merken müssen, ist das Array, in dem die Maxima gespeichert sind. Die Länge dieses Arrays hängt vom Wert von k ab, d. h. von der Anzahl der Bits des Vektors, die wir als Gruppenindex verwenden. Für ein gegebenes k gibt es insgesamt 2k verschiedene Gruppen, und daher hat das Array der Maxima eine Länge von 2k. In der Implementierung haben wir diesen Wert num_buckets genannt.

Wie groß muss eine Zelle des Arrays sein? Wir werden die Längen der Null-Suffixe darin speichern. Ich kann Ihnen im Voraus sagen, dass ein 64-Bit-Hash wahrscheinlich für jedes denkbare Multiset der Welt ausreicht, also müssen wir in der Lage sein, Zahlen von 0 (ein Vektor aller Einsen) bis 64 (ein Vektor aller Nullen) in diesem Array zu speichern. Wenn wir außerdem davon ausgehen, dass k immer größer als Null ist, dann reicht es aus, Zahlen von 0 bis 63 zu speichern. Dafür brauchen wir bitte nur 6 Bits, denn 26 = 64.

Ja, wir brauchen nur ein "Array", in dem eine Zelle 6 Bit groß ist. Ich kann Ihnen auch sagen, dass k=10 ausreicht, um eine ziemlich gute Schätzung der Kardinalität in der Größenordnung von Hunderten von Millionen zu erhalten. Ein so angelegter Algorithmus würde ein Array der Größe 210 = 1024 erzeugen, in dem jede Zelle 6 Bits belegt. Insgesamt würde dieses Feld 6144 Bits belegen, was 768 Bytes entspricht. Nicht einmal ein Kilobyte.

Und das war's.

Wir brauchen nichts weiter zu speichern, wir können die berechneten Hashes sofort verwerfen, wir müssen nur die Anzahl der Nullen am Ende des Vektors kennen.

Wenn Sie eine größere Hash-Funktion verwenden würden, die z. B. 128 Bit zurückliefert, würde sich der Speicherplatzbedarf nicht wesentlich ändern. Tatsächlich müssten wir Zahlen von 0 bis 127 speichern, wofür wir nur 7 Bits benötigen. Der Speicherbedarf wird also hauptsächlich durch den Parameter k, d. h. die Anzahl der Gruppen, bestimmt.

LogLog ist besonders nützlich, wenn es darum geht, Multisets mit sehr großer Kardinalität zu berechnen. Wie im obigen einfachen Beispiel zu sehen ist, kann LogLog Multisets mit kleiner Kardinalität nicht optimal verarbeiten. Dies lässt sich jedoch ändern, indem man einen anderen Algorithmus zur Schätzung verwendet, wenn die Multimenge eine geringe Kardinalität aufweist, wie z. B. den oben beschriebenen linearen Zählalgorithmus. Auch dies wird beim nächsten Mal besprochen.

Ressourcen: