Datenströme machten exaktes Zählen unpraktisch: Für jedes mögliche Element einen Zähler zu führen, konnte mehr Speicher kosten, als der Stream-Prozessor zur Verfügung hatte. Ältere Zusammenfassungen verbesserten den Speicherbedarf, doch viele Schranken waren noch zu teuer.
Count-Min Sketch verwendete eine kleine Matrix von Zählern und mehrere Hash-Funktionen. Aktualisierungen waren Inkremente in konstanter Zeit; Punkt-, Bereichs- und Skalarprodukt-Abfragen waren approximativ, aber schnell und sublinear im Speicher.
Die Publikationsseite von Cormode und Muthukrishnan fasst die Verbesserung zusammen: Bei mehreren Stream-Problemen verbesserte sich die Speicher- oder Zeitschranke typischerweise von einem Faktor von 1/Epsilon zum Quadrat auf 1/Epsilon.
Jeden Fehler nach oben zeigen lassen
Hash-Kollisionen werden toleriert statt verhindert, was den Speicher fest und vorhersehbar macht.
Das Nehmen des Minimums über die Zeilen verwandelt viele verrauschte Zähler in eine begrenzte Überschätzung.
Die Struktur unterstützt mehrere Stream-Abfragen, nicht nur einen einzelnen Heavy-Hitter-Bericht.
Ihre kleine, zusammenführbare Form machte sie praktisch für Telemetrie, Werbung, Netzwerke und Datenbanken.
Approximation ist leichter zu betreiben, wenn ihre Fehler eine Richtung haben; ein einseitiger Fehler erlaubt es nachgelagerten Systemen, das Ergebnis als sichere obere Schätzung zu behandeln.
Count-Min Sketch wurde zu einem der Standard-Sketches für die Häufigkeitsschätzung in Streaming-Systemen. Der kluge Schachzug bestand nicht darin, so zu tun, als verschwänden Kollisionen; er ordnete Kollisionen so an, dass ihr Schaden messbar und einseitig war.
DEN BELEGEN FOLGEN
Die Quellen
- An improved data stream summary: The count-min sketch and its applications University of Oxford · cs.ox.ac.uk