Der sogenannte Count-Min Sketch weißt eine deutliche Ähnlichkeit zum zählenden Bloom-Filter auf (daher am besten zuvor diesen Post lesen). Es geht darum, abschätzen zu können, wie oft ein bestimmtes Element in einem sehr großen Datenstrom, den wir aus Platzgründen nicht in einer HashMap speichern können oder wollen, vorgekommen ist.
Folgendes Beispiel soll die Anwendung illustrieren: angenommen, wir haben A, C, D, C, A, B, B, A, B, A, P, P als Datenstrom, dann ergibt eine Zählung der Elemente folgendes Ergebnis: 4 x A, 3 x B, 2 x C, 1 x D und 2 x P. Eine konkrete Anwendung für dieses Szenario wäre z.B. das Zählen der Page-Impressions auf diversen Unterseiten einer großen Webseite.
Noch einmal anders ausgedrückt: wir möchten in einer sehr großen Multimenge zählen, wie oft jedes Mengenelement vorgekommen ist.
Noch einmal anders ausgedrückt: wir möchten in einer sehr großen Multimenge zählen, wie oft jedes Mengenelement vorgekommen ist.
Aufbau und Mechanik
Auch der Count-Min Sketch ist eine probablistische Datenstruktur, die auf Hash-Funktionen basiert. Verwenden wir (wie beim Bloom-Filter) d = 2 beliebige Hash-Funktionen für die ASCII-Werte unserer Buchstaben (A = 65, B = 66, C = 67, D = 68, P = 80) im Datenstrom:
h1 = ASCII-Wert modulo 8
h2 = (ASCII-Wert - 65) * 2 modulo 8
Anders als beim Bloom-Filter erhält allerdings jede Hash-Funktion ihr eigenes Zähler-Array za1 und za2 mit jeweils w Einträgen. Beide werden initial vollständig mit Nullen befüllt:
za1: 0 0 0 0 0 0 0 0
za2: 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
Nun berechnen wir die Hash-Werte für unseren Datenstrom:
h1: h2:
A -> 1 A -> 0
B -> 2 B -> 2
C -> 3 C -> 4
D -> 4 D -> 6
P -> 0 P -> 6
Und aktualisieren za1 und za2 der Reihe nach, indem wir an der entsprechenden Stelle eins hinzu addieren z.B. für das erste A:
za1: 0 1 0 0 0 0 0 0
za2: 1 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7
Für das erste C:
za1: 0 1 0 1 0 0 0 0
za2: 1 0 0 0 1 0 0 0
0 1 2 3 4 5 6 7
Für das D:
za1: 0 1 0 1 1 0 0 0
za2: 1 0 0 0 1 0 1 0
0 1 2 3 4 5 6 7
Für das zweite C:
za1: 0 1 0 2 1 0 0 0
za2: 1 0 0 0 2 0 1 0
0 1 2 3 4 5 6 7
Und so weiter, bis wir schließlich folgende beiden Arrays erhalten:
za1: 2 4 3 2 1 0 0 0
za2: 4 0 3 0 2 0 3 0
0 1 2 3 4 5 6 7
Wir sehen, dass sich dabei durch die Kollision der Hash-Werte von D und P in h2 eine kleine "Verfälschung" (rot markiert) ergibt. Diese ist allerdings insofern (noch) nicht von Bedeutung, als wir bei einer Abfrage immer den kleinsten Wert aus beiden Arrays zurückgeben, also min(za1, za2) an dem Index, der durch die jeweilige Hash-Funktion geliefert wird.
Für A wäre also za1[1] = 4 und za2[0] = 4, hier besteht sogar eine Übereinstimmung. Betrachten wir uns D, ergibt sich folgendes Bild: za1[4] = 1 und za2[6] = 3, der Eintrag in za2 wurde durch D verfälscht, wir geben aber den kleinsten der beiden Werte zurück und erhalten als Abschätzung für die Anzahl der Ds korrekterweise eine Eins.
Dieser günstige Umstand wird leider nicht dauerhaft erhalten bleiben, angenommen, als nächstes taucht ein X (ASCII = 88) im Datenstrom auf, hier errechnet h1 eine 0 und h2 eine 6, so dass unsere Arrays nun wie folgt belegt wären:
Dieser günstige Umstand wird leider nicht dauerhaft erhalten bleiben, angenommen, als nächstes taucht ein X (ASCII = 88) im Datenstrom auf, hier errechnet h1 eine 0 und h2 eine 6, so dass unsere Arrays nun wie folgt belegt wären:
za1: 3 4 3 2 1 0 0 0
za2: 4 0 3 0 2 0 4 0
0 1 2 3 4 5 6 7
Nun würde sowohl eine Abfrage für X, als auch eine Abfrage für P ein überschätztes Ergebnis, nämlich jeweils 3 liefern, womit wir die Schwäche des Count-Min-Sketch-Ansatzes aufgedeckt haben.
Eine weitere interessante Eigenschaft des Count-Min Sketchs ist, dass er durch die Verwendung der Hash-Funktionen die gespeicherten Daten anonymisiert. Unter Datenschutzgesichtspunkten lässt sich das durchaus als Vorteil sehen, da es zwar beispielsweise möglich ist, zu prüfen, ob eine gegebene IP-Adresse bereits gespeichert wurde, es kann aber keine Liste von vorhandenen IP-Adressen generiert werden.
Genauigkeit
Durch eine Vergrößerung des Bit-Arrays und eine Erhöhung der Anzahl an Hash-Funktionen lässt sich die Wahrscheinlichkeit für Kollisionen und damit False Positives natürlich verringern. Die Berechnung der Zahl der Hash-Funktionen d und der Anzahl der jeweils benötigten Zähler w ist beispielsweise in [2] erklärt, kurz gesagt müssen 2/w gleich der gewünschten Fehlerwahrscheinlichkeit und (1/2)d gleich dem gewünschten Konfidenzniveau sein.
Als Beispiel: wir möchten N Elemente per Count-Min Sketch zählen, dabei eine maximale relative Abweichung in der Zählung von 0,1% bei einer 99,5%igen Sicherheit tolerieren; dies erfordert folgende Berechnungen:
w = 2 / 0,001 = 2.000
d = log(0,005) / log(1/2) ~ 8
Somit erhalten wir bei 4 Byte-Integer-Zählern einen Speicherbedarf von w * d * 4 = 64 kByte für das Zählerrarray und z.B. bei N = 100 Millionen eine maximale absolute Zählerabweichung von rund 100.000.
Literaturverweise
- das Original-Paper (schwer verdaulich)
- ein leichter verdauliches Paper
Keine Kommentare:
Kommentar veröffentlichen