Neuer Algorithmus zum effizienten Zählen eindeutiger Elemente

 (quantamagazine.org)
2 Punkte von GN⁺ 2024-05-17 | 1 Kommentare | Auf WhatsApp teilen
  • Der CVM-Algorithmus schätzt die Anzahl unterschiedlicher Elemente in langen Datenströmen und kann so die Zahl eindeutiger Elemente bestimmen, ohne die gesamte Liste zu speichern
  • Im Fokus steht das Distinct-Elements-Problem, bei dem die gesamte Eingabe den verfügbaren Speicher übersteigt; das Verfahren kann auf große Logs oder Event-Streams mit vielen Duplikaten angewendet werden
  • Es behält nur einen Teil der Elemente im begrenzten Speicher und führt jedes Mal, wenn der Speicher voll ist, zufällige Löschungen durch, damit die Wahrscheinlichkeit, dass ein Element erhalten bleibt, für alle gleich ist
  • Im Hamlet-Beispiel ergab sich mit einem Speicher für 100 Wörter über 5 Durchläufe ein Durchschnittswert von 3.955, nahe an der tatsächlichen Zahl von 3.967 eindeutigen Wörtern; mit einem Speicher für 1.000 Wörter verbesserte sich der Mittelwert auf 3.964
  • Mit mehr Speicher steigt die Genauigkeit, und wenn genug Platz für alle eindeutigen Elemente vorhanden ist, sind auch 100 % Genauigkeit möglich

Eindeutige Elemente in langen Datenströmen zählen

  • Ziel ist es, in einer langen Liste von nacheinander eintreffenden Elementen die Anzahl eindeutiger Elemente ohne Duplikate effizient zu schätzen
  • Der einfachste Ansatz wäre, alle bisher gesehenen Elemente zu speichern und jedes neue Element mit der bestehenden Liste zu vergleichen
    • Bei einer Wildtiererhebung müsste man ständig die Liste bereits gesehener Tierfotos prüfen
    • Wenn die Liste wie bei den täglichen Facebook-Logins in die Milliarden geht, werden Speicherung und Vergleich schwierig
  • CVM ist nach Sourav Chakraborty, Vinodchandran Variyam und Kuldeep Meel benannt
  • Das Verfahren lässt sich auf sequenziell eintreffende Listen anwenden, etwa Wörter, Produkte auf einem Förderband oder Fahrzeuge auf einer Autobahn

Die Kernidee des CVM-Algorithmus

  • CVM speichert nicht alle Elemente, sondern nur einen Teil davon, der in den begrenzten Speicher passt
  • Um die Wahrscheinlichkeit zu steuern, dass jedes eindeutige Element in der Endliste verbleibt, nutzt der Algorithmus Zufälligkeit
  • Andrew McGregor meint, der Algorithmus sei so einfach und leicht zu implementieren, dass er ein grundlegender Ansatz für praktische Distinct-Elements-Probleme werden könnte

So funktioniert es am Beispiel von Hamlet

  • Hamlet enthält insgesamt 30.557 Wörter, und der Algorithmus schätzt daraus die Anzahl eindeutiger Wörter
  • Angenommen, der Speicher ist ein Whiteboard für 100 Wörter: Zunächst werden, unter Überspringen von Wiederholungen, die ersten 100 eindeutigen Wörter notiert
  • Ist der Platz voll, wird für jedes Wort eine Münze geworfen
    • Bei Kopf bleibt das Wort erhalten
    • Bei Zahl wird das Wort gelöscht
    • Nach dieser Vorstufe bleiben etwa 50 eindeutige Wörter übrig

Mit jeder Runde strengere Bedingungen zum Behalten

  • In Runde 1 werden neue Wörter weiter hinzugefügt; taucht ein Wort erneut auf, das schon in der Liste steht, wird eine Münze geworfen und bei Zahl gelöscht
  • Wenn die Liste wieder 100 Wörter erreicht, endet Runde 1, indem gemäß 100 Münzwürfen etwa die Hälfte gelöscht wird
  • Ab Runde 2 wird es für Wörter schwieriger, zu überleben
    • Erscheint ein Wiederholungswort, wird es bei Zahl gelöscht
    • Fällt Kopf, wird noch einmal geworfen, und nur bei einem zweiten Kopf bleibt es erhalten
  • In der dritten Runde sind 3 Köpfe in Folge nötig, in der vierten Runde 4 Köpfe in Folge
  • Allgemein beträgt am Ende der k-ten Runde die Wahrscheinlichkeit, dass ein Wort verbleibt, 1/2^k

Berechnung des Schätzwerts und Versuchsergebnisse

  • Teilt man die Zahl der Wörter in der Endliste durch die Wahrscheinlichkeit, mit der sie erhalten bleiben, erhält man eine Schätzung der Gesamtzahl eindeutiger Wörter
  • Wenn zum Beispiel nach 6 Runden 61 Wörter übrig sind, ergibt die Division durch die Wahrscheinlichkeit 1/2^6 den Schätzwert 3.904
  • Die tatsächliche Zahl eindeutiger Wörter in Hamlet beträgt 3.967
  • Je größer der Speicher, desto näher liegt der Schätzwert am tatsächlichen Wert
    • Bei einem Speicher für 100 Wörter lag der Durchschnittswert über 5 Läufe bei 3.955
    • Bei einem Speicher für 1.000 Wörter lag der Mittelwert bei 3.964
  • Variyam und seine Kollegen haben mathematisch bewiesen, dass die Genauigkeit dieser Technik mit der Speichergröße skaliert

Einfach, aber nicht trivial

  • CVM gilt als wichtiger Fortschritt beim seit mehr als 40 Jahren erforschten Distinct-Elements-Problem
  • William Kuszmaul meint, dass selbst für sehr grundlegende und gut untersuchte Probleme noch einfache, aber nicht leicht naheliegende Lösungen existieren können

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-17
Hacker-News-Kommentare

  • Ich habe zusammen mit den Autoren an einer Implementierung der DNF-Volumenzählungs-Version dieses Algorithmus mitgearbeitet. Der zugehörige Artikel ist hier: https://www.msoos.org/2023/09/pepin-our-probabilistic-approx...
    Der Code ist hier: https://github.com/meelgroup/pepin
    Der Algorithmus ist absurd schnell, so sehr, dass oft 30 % der Gesamtzeit für Datei-Lese-I/O draufgehen. Zur Einordnung: Knuth hat ebenfalls zum Algorithmus beigetragen, und seine Notizen sind hier: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
    Ich habe dafür einen ganzen Monat an der TAOCP-Arbeit pausiert, und es war genauso unglaublich beeindruckend, wie man es sich vorstellt

    • Wirklich interessant, und ich interessiere mich sehr für außergewöhnlich talentierte Menschen. Ich frage mich, warum Knuth so beeindruckend wirkte. Gab es einen besonderen Moment, lag es an der Geschwindigkeit, mit der er Ideen verstand, oder an seiner Fähigkeit, Dinge einfach zu erklären?
    • Das wirkt dumm. Sehr dumm sogar — aber übersehe ich etwas? Das ist kein Zählen, sondern einfach nur Sampling, und wenn man tatsächlich alle unterschiedlichen Wörter zählen will, scheint sich der Speicherverbrauch gegenüber einfachem Zählen nicht zu unterscheiden
    • Du scheinst es vielleicht zu wissen, deshalb frage ich mich, warum man nicht stattdessen nach größeren Zählwerten sortiert und dann, wenn es voll ist, die untere Hälfte verwirft. Das ist für andere vielleicht obvious, aber ich würde den Grund gern verstehen
    • Ich frage mich, was die wichtigste Anwendung dieses Algorithmus ist
    • Jetzt gibt es also jemanden, den man dafür verantwortlich machen kann, dass sich Knuths nächstes Buch verspätet :)

  • Dieser Algorithmus wirkt ähnlich wie HyperLogLog, das auch im Paper zitiert wird. Er verwendet dieselbe Einsicht, bei der man aufeinanderfolgende Kopf-/Zahl-Ergebnisse verfolgt, um eine Schätzung zu erhalten, dreht die Idee aber um und macht daraus einen einfacheren Algorithmus, der gespeicherte Werte je nach Serie von Münzwurfergebnissen verwirft
    In Streaming-Szenarien arbeitet er besonders effizient, sodass man eine Art „Zähler“ für die Anzahl unterschiedlicher Elemente mit Fehlerrate aufrechterhalten kann
    Der Vorteil von HyperLogLog ist, dass es in gewisser Weise wie ein Hash-Set funktioniert. Man kann Elemente hinzufügen und die Anzahl unterschiedlicher Elemente zählen, und wichtig ist, dass man zwei HLLs zu einer Vereinigungsmenge zusammenführen kann, während der Speicher selbst bei Mengen mit Milliarden von Einträgen auf wenige KB fest bleibt. In verteilten Datenspeichern nutzen die Cardinality-Aggregation in Elasticsearch/OpenSearch sowie PFADD/PFMERGE/PFCOUNT in Redis/Redict diesen Trick
    Ich weiß nicht genau, wie sich der CVM-Algorithmus im Vergleich zu HLL schlägt, aber wenn Knuth ihn begutachtet hat und selbst Studierende im Grundstudium ihn leicht implementieren können, scheint es ein ziemlich guter Algorithmus zu sein

    • HLL kann sowohl die Vereinigung als auch die Schnittmenge zweier HLLs schätzen und lässt sich daher auch zur Kardinalitätsschätzung von Joins verwenden
      http://oertl.github.io/hyperloglog-sketch-estimation-paper/
    • Diese Datenstrukturen lassen sich ebenfalls zusammenführen. Wenn die „Runden“ der beiden zu verschmelzenden Instanzen unterschiedlich sind, bringt man die frühere Runde einfach um die Rundendifferenz weiter — also indem man zufällig die Hälfte verwirft. Danach fügt man die Werte einer Liste in die andere ein und ignoriert Duplikate. Wenn das Ergebnis zu groß wird, verwirft man wieder zufällig die Hälfte und erhöht die Rundennummer
      Ich habe diesen Algorithmus in meinem vorherigen Job genau so implementiert, und wir haben neben jedem Wert auch eine Schätzung gespeichert, wie oft dieser Wert aufgetreten ist. Dadurch konnten wir eine approximative Liste der häufigsten Werte samt geschätzter Häufigkeiten erstellen
    • Wenn ich in meinen alten Studienerinnerungen krame, frage ich mich: In welchem Verhältnis stehen die hier erwähnten HLL und CVM zu dem Reservoir Sampling, das wir früher gelernt haben?
      Als ich früher in einem Krankenhaus gearbeitet habe, habe ich einmal Reservoir Sampling verwendet, um aus auf DAT-Bändern gespeicherten Datensätzen eine kleine Teilmenge zu erstellen

  • Das Lesen des Papers dauerte fast genauso lange wie das Lesen des Blogposts, und das Paper war nützlicher.
    https://arxiv.org/pdf/2301.10191
    Es geht um die Schätzung der Kardinalität der Menge von Elementen aus einem Stream. Der Algorithmus ist so einfach, dass man ihn schon beim Lesen des Papers selbst implementieren und damit herumspielen kann.
    Die Autoren sagen ausdrücklich, dass die Zielgruppe und der Zweck dieses Algorithmus Studierende im Bachelor und Lehrbücher sind.

    • Der Untertitel des Papers, „An Algorithm for the (Text) Book“, scheint sich auf Paul Erdős' berühmte Formulierung zu beziehen, dass etwas wegen seiner Schlichtheit und Schönheit wie ein Beweis „aus The Book“ wirke.
      Da Knuth es persönlich begutachtet hat, hielt er den Algorithmus vielleicht für so etwas. Falls ja, wirkt es etwas unbescheiden, das in den Titel zu schreiben, aber es ist durchaus etwas, womit man angeben darf.
      Ich dachte ursprünglich, diese Formulierung stamme von Knuth, aber meine Erinnerung war falsch.
    • Mehr als die Hälfte des Blogposts war padding. Dass der Algorithmus so einfach ist, dass man daraus nur schwer einen langen Blogpost machen kann, ist eigentlich etwas Gutes.
    • Ich stimme zu, dass das Paper besser ist als der Blogpost, aber ein Kritikpunkt am CVM-Paper ist, dass es eine Abbruchbedingung enthält. In Knuths CVM-Notizen aus einem anderen Thread gibt es einfach eine Schleife, damit beim Schritt des Halbierens des Reservoirs wieder mehr Platz entsteht.
      Eine einfache Schleife zu verwenden erscheint weniger umständlich, als https://en.wikipedia.org/wiki/Up_tack zu erklären. [1]
      [1] https://news.ycombinator.com/item?id=40388878
    • Ich habe früher Informatik gemacht, aber vielleicht ist mein Gehirn inzwischen glattpoliert, denn das hier wirkt unnötig verwirrend.
      Erstens scheint die Behandlung von contradiction einfach ein Fehler oder Panic zu sein, also verstehe ich nicht, warum es so ausgedrückt wird. Außerdem ist die Annahme 1..m verwirrend. Ich war mir nicht sicher, ob man die Größe im Voraus kennen muss oder nicht, aber bei genauerem Lesen wohl eher nicht. Man wählt einen Schwellenwert, und die Wahrscheinlichkeit ändert sich mit der Stream-Größe, aber die Beschreibung des Algorithmus ist so geschrieben, als gäbe es nur eine einzige Ausgabe, was verwirrend ist.
      Auch Chernoff-Schranken und delta/epsilon werden im Paper überhaupt nicht erklärt, was es noch verwirrender macht. Mein in Go ausprobierter Code ist hier: https://github.com/betamos/distinct
      Es ergibt viel mehr Sinn, den Teil mit den Schwellenwerten in einen helper auszulagern, als versehentlich zu viel Speicher zu allozieren. Es sollte wohl auch eine Methode geben, die Konfidenz oder Fehlerrate abzuschätzen. Niemand kennt die Stream-Größe im Voraus, daher wäre es natürlicher, diesen Wert im Verlauf zu aktualisieren.
    • Wenn „für Studierende im Bachelor und Lehrbücher“ nicht bedeutet, dass es einfach genug ist, um dort verwendet zu werden, sondern dass es tatsächlich nur dort nützlich ist, dann wäre eine Erklärung hilfreich, warum es für Fachleute nicht nützlich ist und nur für Studierende.

  • Wenn man an das Thema des Papers denkt, ist die Fußnote besonders reizvoll.
    Die Autoren sagen, sie hätten statt der alten Konvention der alphabetischen Reihenfolge der Autorennamen eine zufällige Reihenfolge gewählt und diese mit r⃝ gekennzeichnet. Ein öffentlich überprüfbarer Nachweis der Zufallsauswahl ist hier: https://www.aeaweb.org/journals/policies/random-author-order...
    [0]: https://arxiv.org/pdf/2301.10191

  • Ist die Beschreibung des Algorithmus nicht falsch?
    Wenn man gemäß der Beschreibung „Wenn man ein Wort trifft, das bereits in der Liste steht, wirft man erneut eine Münze, und bei Zahl löscht man das Wort“ tatsächlich „prüfen, ob es in der Liste ist, und dann löschen“ implementiert, läuft es ungefähr 20 Iterationen lang und liefert einen unsinnigen Schätzwert wie 772800512.
    Wenn man stattdessen das Wort zuerst speichert und dann dasselbe Wort wieder löscht, erhält man 7240, also nahe an der tatsächlichen Zahl unterschiedlicher Wörter von 7233. Das heißt, die Reihenfolge ist in der Beschreibung wichtig und scheint falsch vermittelt worden zu sein.

    • Ich hatte dasselbe Problem. Wenn man nur die Erklärung in Quanta Magazine nimmt und nicht das arXiv-Paper anschaut, bekommt man immer Schätzwerte wie 461746372167462146216468796214962164.
      Nachdem ich das Paper gelesen hatte, bekam ich den korrekten Schätzwert, und das Problem war ein kleines else. Die Quanta-Erklärung liest sich so, als heiße es „wenn es nicht in der Liste ist, füge es hinzu, andernfalls entferne es mit einer gewissen Wahrscheinlichkeit“, aber die korrekte Implementierung muss die Wahrscheinlichkeitsbedingung danach anwenden, unabhängig davon, ob etwas hinzugefügt wurde.
    • Ich habe das gerade selbst durchgearbeitet und kam her, um zu sehen, ob andere dasselbe Problem hatten, und ja. Wenn man es so umsetzt, wie es beschrieben ist, ist es falsch; man muss in jeder Runde den neuen Wert hinzufügen, ihn dann probabilistisch ausdünnen und, wenn das Speicherlimit erreicht ist, eine zufällige Hälfte aus der gesamten Menge entfernen.

  • Die Schätzung der Anzahl unterschiedlicher Elemente in einer Menge und das Zählen der Anzahl unterschiedlicher Elemente in einer Menge sind sehr unterschiedliche Dinge. Schöne Methode, aber der Titel ist nicht gut.

    • So unterschiedlich sind die beiden nicht. Alle Zählverfahren in der realen Welt haben eine Fehlerrate ungleich null, daher werden die beiden Begriffe in den meisten Kontexten austauschbar verwendet.
      Zum Beispiel sagt man bei Wahlen, dass man „Stimmen zählt“, aber wenn es knapp ist, macht man eine „Neuauszählung“, und man erwartet völlig, dass dabei eine leicht andere Zahl herauskommen kann als beim ursprünglichen Count. Dann ist auch das Zählen von Stimmen in Wirklichkeit eine Schätzung von Stimmen, und die Neuauszählung ist nur eine Schätzung mit engeren Fehlerschranken.
      Der Mythos der „countless stones“ (https://en.wikipedia.org/wiki/Countless_stones) wirkt ebenfalls wie eine volkstümliche Erinnerung daran, dass man sich selbst bei etwas so Großem, Solidem und Statischem wie einem Steinkreis nicht zu sicher sein sollte, es korrekt gezählt zu haben.
      Fälle, in denen Zählen keine Schätzung ist, sind im Wesentlichen auf mathematische Situationen beschränkt, in denen man garantieren kann, dass man alle Elemente ohne Auslassung erfasst und die Identität keines Elements mit einem anderen verwechselt hat.
    • Bei relativ kleinen Zahlen stimmt das. Aber bei sehr großen Zahlen wird Schätzen normalerweise als gleichwertig mit Zählen behandelt, und das Ergebnis wird dann auch nicht als Integer, sondern in wissenschaftlicher Notation, also eher wie eine Gleitkommazahl, ausgedrückt.
      Ein Mol ist zum Beispiel eine ganze Zahl, aber sein Wert ist nur näherungsweise bekannt, und niemand kümmert sich um den exakten Wert.
    • Das ist keine estimation, sondern eine approximation.

  • Ich mag solche Beispiele für Denken außerhalb der üblichen Bahnen wirklich sehr. Vielleicht auch gerade deshalb, weil ich beruflich nicht besonders gut darin bin. Wichtig ist nicht nur, die richtige Methode zur Lösung eines Problems zu lernen, sondern den Prozess, die Frage zu finden, die das vorliegende Problem einfacher macht oder manchmal überhaupt erst lösbar.
    Hier ist die Schlüsselfrage: „Wir brauchen keine exakte Zahl; es reicht, einen probabilistischen Bereich innerhalb definierter Parameter zu bestimmen.“ Bei anderen Problemen wird es andere Fragen geben. Ich hoffe, dass man, wenn man genügend solcher Beispiele sieht, den Denkprozess verinnerlichen und richtig anwenden kann.

    • Fairerweise muss man sagen: Das hier wurde von einem universitären Forschungsteam gemacht. Also buchstäblich von einem Team von Leuten, die den ganzen Tag lang ein einziges Thema mit wissenschaftlicher Methode wiederholt untersuchen können.
      Wenn man in einem großen Unternehmen dafür bezahlt würde, den ganzen Tag mit genauso klugen Ingenieuren vor einem Whiteboard zu sitzen, könnte man sicher ebenfalls etwas hervorbringen, das für die Welt wie eine „Lösung außerhalb der üblichen Bahnen“ aussieht.
      Aber die meisten von uns werden dafür bezahlt, an einer JIRA-Fließbandarbeit zu sitzen, daher ist die Zeit begrenzt, in der man an nur einem Problem experimentieren kann.
    • Üblicherweise nennt man das wohl laterales Denken. Edward de Bono hat ein paar Bücher dazu geschrieben, die interessant sein könnten.

  • Das Beispiel „Was ist, wenn man die Anzahl unterschiedlicher Nutzer zählen will, die sich täglich bei Facebook einloggen, und manche Nutzer sich über mehrere Geräte und zu verschiedenen Zeitpunkten anmelden?“ scheint mir als reales Einsatzszenario für diesen Algorithmus nicht besonders passend.
    Wenn man beim Entwurf des Login-Prozesses schon weiß, dass man diese Information braucht, ist es einfach: Man speichert für jedes Konto das Datum des letzten Logins und erhöht den Zähler für eindeutige Nutzer nur dann, wenn der gespeicherte Wert sich vom aktuellen Datum unterscheidet.
    Selbst wenn nicht, könnte man den Strom der Login-Ereignisse später wohl aus der Datenbank „nachspielen“ und analysieren. Anders wäre es vielleicht, wenn sich bereits Daten über viele Jahre angesammelt haben.

    • Diese Methode erfordert das Nachverfolgen des „Datums des letzten Logins“ für jedes Konto und benötigt daher Speicher proportional zur Anzahl der Nutzer. Der Kern dieses Algorithmus ist, dass er mit viel kleinerem festem Speicher arbeitet.

  • Zum Thema Zählen möchte ich einen effizienten und zudem leicht zu implementierenden Algorithmus erwähnen, um die Top-k-Elemente in einem Stream zu finden. Er scheint weniger bekannt zu sein, als er sollte.
    A Simple Algorithm for Finding Frequent Elements in Streams and Bags
    Karp, Shenker & Papadimitriou
    https://www.cs.umd.edu/~samir/498/karp.pdf

    • Die Formulierung „Top-k-Elemente in einem Stream“ klingt anders als die Beschreibung im Abstract. Dort steht, dass in einer sehr langen Symbolfolge aus einem großen Alphabet Symbole mit einer Häufigkeit über einem gegebenen Schwellenwert gefunden werden.
      Deine Beschreibung klingt so, als würde man eine feste Zahl k von Elementen finden und eine Garantie bekommen, dass genau diese die Top-Elemente sind. Das Abstract klingt dagegen so, als würden Elemente gefunden, die eine Bedingung größer als ein bestimmter Wert k erfüllen, wobei man ihre Anzahl im Voraus nicht kennt.
      Es wirkt wie der Unterschied zwischen „die 100 ältesten Nutzer finden“ und „alle Nutzer über 30 finden“. Verstehe ich deine Aussage oder das Abstract falsch? Englisch ist nicht meine Muttersprache, daher bin ich unsicher.

  • Informatiker haben also eine Methode erfunden, um die Größe einer Teilmenge speichereffizient zu schätzen.

    • Wenn sich ein Schätzwert mit weniger Münzwürfen bestimmen lässt, sieht das auch schneller aus. Vielleicht muss man nicht einmal das ganze „Buch“ bis zum Ende durchgehen, um die Zahl unterschiedlicher Wörter zu schätzen.
    • Entscheidend ist hier die Teilmenge, nämlich die Teilmenge der eindeutigen Elemente.