Datenstrukturdienstag: Eine meiner lieblings-Strukturen, der Bloom-Filter.
Eine wichtige Eigenschaft eines Bloom-Filters ist die False-Positive-Rate. Das ist die Wahrscheinlichkeit für False-Positives. Zu dieser Wahrscheinlichkeit gab es 30 Jahre später noch eine neue Formel, da die ursprüngliche wohl fehlerhaft war. Hier ist ein Writeup dazu. Hier ist noch ein Paper dazu.
Was man in der Praxis für Probleme mit einem Bloom-Filter haben kann, hat Cloudflare mal aufgeschrieben.
Datenstrukturdienstag: Letzte Woche gab’s den Bloom-Filter, diese Woche muss man dann wohl den Cuckoo-Filter erwähnen.
Großer Unterschied (IMHO): Man kann auch Einträge wieder löschen.
Datenstrukturdienstag: Dieses Mal gibt es wieder eine probabilistische Datenstruktur: Count–min-Sketch. Damit kann man (probabilistisch) schätzen, wie oft ein Element vorgekommen ist, z. B. wenn man einen Datenstrom hat und vorbeigehende Dinge zählt.
Datenstrukturdienstag: Letzte Woche: Zählen, wie oft bestimmte Elemente vorkamen. Diese Woche: Zählen, wie viele Elemente in einer Menge enthalten sind.
Verwenden kann man dafür HyperLogLog (ja, wieder probabilistisch).
Anwendungsfall: Ihr habt eine Menge, zu der ständig neue Elemente hinzukommen. Ihr braucht euch nicht jedes Element merken. Aber es kann sein, dass ein Element, das eigentlich schon drin ist, noch mal hinzugefügt werden soll. Ihr wollt dieses Element nicht doppelt zählen (Fachbegriff Count-Distinct-Problem).
Konkret wollt ihr vielleicht die Anzahl der Aufrufe eines Videos zählen und nimmt dabei die ID des Users, der es angesehen hat, als Kriterium. Schaut sich die Person es noch mal an, wollt ihr sie nicht noch mal zählen. HLL hat dabei einen sehr langsam wachsenden Speicherbedarf (ursprünglich log(log(n)), daher der Name) und kann in O(1) Elemente hinzufügen.
In der Praxis muss man das natürlich nicht selber bauen. Redis hat das built-in. Und für jede Sprache gibt’s das sicherlich auch als Library.
HLL wird natürlich bei den “ganz großen” verwendet (Reddit hat hier berichtet, wie sie ihre Views zählten; habe gehört, dass sie es mittlerweile nicht mehr so machen). Diese Datenstruktur ist auch der Grund, warum Video-Views oder Upvote-Counts meistens nicht die genaue Zahl wiederspiegeln. HLL hat eine Fehlerrate von ~2%.
Es gibt von HLL noch weitere Abwandlungen, z. B. HLL++.