2019-10-05, 20:30–21:00, Proxima b
Eine Einführung in Probabilistische Datenstrukturen, was für Probleme sie lösen und welche Trade-Offs dabei eine Rolle spielen.
Reddit, Facebook, Twitter und co. haben unheimlich große Nutzer- und Zugriffszahlen. Diese zu zählen stellt selbst diese großen Konzerne vor ein Problem, denn einfache Zugriffstabellen können dabei an ihr Limit kommen.
Glücklicherweise brauchen wir nicht überall genauen Zahlen – meist reicht eine Schätzung, die „gut genug“ ist.
Für diese Art von Problemen wurden probabilistische Datenstrukturen erfunden.
Auf dem Weg zu einem probabilistischen Zähler schauen wir uns ein ähnliches Problem an:
Wie überprüft Chrome eigentlich, ob eine Webseite in einer Blockiste ist?
Am Ende dieses Talks haben wir zwei Lösungen kennengelernt, die uns abschätzende Antworten auf die Fragen „Wie viele Elemente sind in unserer Menge?“ (HyperLogLog) und „Ist dieses Element enthalten?“ (Bloom-Filter) geben können.