Zählen von Objekten in einem Datenstrom - Dummies

Das Lernen, Objekte in einem Stream zu zählen, kann Ihnen dabei helfen, die häufigsten Elemente zu finden oder übliche und ungewöhnliche Ereignisse zu klassifizieren. Dieser Algorithmus nutzt Hash-Funktionen und approximative Skizzen. Dies geschieht nach dem Filtern duplizierter Objekte und dem Zählen einzelner Elemente, die im Datenstrom erschienen sind.

Mit dieser Technik lösen Sie Probleme wie die häufigsten Suchanfragen in einer Suchmaschine, die meistverkauften Artikel eines Onlinehändlers, die sehr beliebten Seiten einer Website oder die volatilsten Aktien (indem Sie die Anzahl der Aktien zählen) verkauft und gekauft).

Sie wenden die Lösung für dieses Problem, Count-Min-Skizze, auf einen Datenstrom an. Es erfordert nur einen Datendurchlauf und speichert so wenig Informationen wie möglich. Dieser Algorithmus wird in vielen realen Situationen angewendet (z. B. beim Analysieren des Netzwerkverkehrs oder beim Verwalten von verteilten Datenflüssen). Das Rezept erfordert die Verwendung einer Reihe von Hash-Funktionen, von denen jede einem Bit-Vektor zugeordnet ist, in einer Weise, die einem Bloom-Filter ähnelt, wie in der Figur gezeigt:

1. Initialisiert alle Bitvektoren in allen Positionen auf Nullen.
2. Wenden Sie die Hashfunktion für jeden Bitvektor an, wenn Sie ein Objekt aus einem Stream empfangen. Verwenden Sie die resultierende numerische Adresse, um den Wert an dieser Position zu erhöhen.
3. Wenden Sie die Hashfunktion auf ein Objekt an und rufen Sie den Wert an der zugehörigen Position ab, wenn Sie gefragt werden, wie häufig ein Objekt geschätzt werden soll. Von allen von den Bitvektoren empfangenen Werten nehmen Sie die kleinste als die Frequenz des Stroms an.

Wie werden Werte in einer Count-Min-Skizze aktualisiert?

Da Kollisionen immer möglich sind, wenn eine Hash-Funktion verwendet wird, insbesondere wenn der zugehörige Bitvektor wenige Slots hat, stellt das Vorhandensein mehrerer Bitvektoren sicher, dass mindestens einer von ihnen den korrekten Wert behält. Der Wert der Wahl sollte der kleinste sein, da er nicht mit falschen positiven Zählungen aufgrund von Kollisionen vermischt ist.