Algorithmus für 'k' 'am häufigsten vorkommende Zahlen

Ich habe nach dem effizientesten (Streaming ??) Algorithmus gesucht, der mir die 'k' am häufigsten vorkommenden Elemente in einem Datenstrom zu einem beliebigen Zeitpunkt angibt. Dieser Beitrag: Algorithmen zum Teilen und Erobern von Datenströmen haben mich interessiert.

Angenommen, es gibt Zahlen: (4,3,5,1,6,2,4,3,8,9,1) und ich frage nach den 3 am häufigsten vorkommenden Zahlen (etwa), dann sollte ich bekomme (3,4,1) als Antwort.

Ich habe versucht, online zu suchen, konnte aber keinen Ort finden, der einen Ansatz bietet und sagt, dass dies der beste ist. Eine triviale Lösung wäre, einen Heap oder einen ausgeglichenen Binärbaum zu verwenden, aber ich denke, es gibt einen besseren Weg und ich wollte wissen, ob er irgendwo dokumentiert ist.

Bearbeiten: Ich bin auf der Suche nach einem Algorithmus, der immer die richtige Antwort liefert, im Gegensatz zu einem Genehmigungsalgorithmus (von dem viele in Suchergebnissen auftauchen), der auf die Verteilung von Daten in der einen oder anderen Weise angewiesen ist

ds.algorithms online-algorithms data-streams Dhruvbird
quelle

Tatsächlich gibt es drei Arten von Algorithmen: exakte, ungefähre und "datenabhängige". Sie haben die letzte Art ausgeschlossen, aber sind ungefähre Algorithmen, die NICHT von der Datenverteilung abhängen, zulässig? Wie ich bereits angedeutet habe, sind Sie wegen bekannter Untergrenzen für dieses Problem in einer Stream-Einstellung in Schwierigkeiten.

Suresh Venkat

Ich war neugierig, ob Algorithmen , die begrenzten Speicher (Streaming - Algorithmen) können tatsächlich tun , was ich wollte , und es scheint , dass sie nicht , wie Sie darauf hingewiesen haben. Auch, ob ein nicht-streaming-genauer Algorithmus bekannt ist, der das Problem in O (n) der garantierten Worst-Case-Zeit löst (zitiert von Cormode und Hadjileftheriou aus dem von Ihnen angegebenen Link): citeseerx.ist.psu. edu / viewdoc / Zusammenfassung doi = 10.1.1.106.7889?

dhruvbird

Antworten:

Es gibt eine umfangreiche Literatur zu diesem Problem. Erstens, auch für , das Problem ist hart: als Alon, Matias und Szegedy zeigen, können Sie nicht besser als konstante Faktor Annäherung an die Frequenz des beliebtestenen Elements erhalten Raum, auch wenn Sie sind bereit, randomisiert zu werden. $k=1$ $o(n)$

Wenn Sie jedoch sicher sind, dass ein Element in mehr als 50% der Fälle vorkommt, gibt es einen einfachen Trick, der konstanten Speicherplatz verwendet und diesen findet (dies ist eine beliebte Google-Rätselfrage). Ganz allgemein können Sie mit einer Verallgemeinerung dieses Tricks Elemente finden, die mehr als mal vorkommen. $n/k$

Eine endgültige Übersicht über das, was über das Problem bekannt ist, ist das Papier von Cormode und Hadjileftheriou aus der VLDB 2008 . Es werden die oben genannten und viele der neuesten Methoden behandelt. Die allgemeine Idee ist, dass Sie eine ungefähre Liste der Top- Elemente können (wobei ungefähre Angabe hier bedeutet, dass Sie möglicherweise Elemente erhalten, deren Anzahl in der Nähe der Anzahl der Top- Elemente liegt). $k$ $k$

Suresh Venkat
quelle

+1. Ich denke , die> 50% des Algorithmus ein bekannter ist (Mehrheits Element - Algorithmus) , wie Sie erwähnt

dhruvbird

Vielen Dank!! Das Papier von Cormode und Hadjileftheriou , dass Sie erwähnt zitiert dieses Papier: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889 , die die gleiche Technik hat , die ich dachte. Es unterhält 2 verkettete Listen; eine nach Frequenz und in ihm eine andere Liste aller Elemente mit der gleichen Frequenz.

dhruvbird

können Sie auf dem mehr als 50 Prozent Algorithmus näher erläutern? und das Google Puzzle? Ich kann dieser schlampigen Argumentation nicht folgen, da Sie sie soeben angesprochen und "den bekannten Trick" nicht vollständig ausgenutzt haben. Vielen Dank.

Hier ist ein Link: userweb.cs.utexas.edu/users/misra/scannedPdf.dir/...

Suresh Venkat

Dies ist ein Kommentar (nicht genug Reputation) zu Suresh Venkats Link userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… : Es sieht so aus, als ob der dort präsentierte Algorithmus einen zweiten Durchgang durch die Daten erfordert, was nicht erlaubt ist Hier. In der Tat sehe ich nicht, wie ein One-Pass-Algorithmus mit O (1) Platzbedarf existieren kann.

Tonyk

Ich empfehle außerdem, Abschnitt 8.1.3 "Frequent-Pattern-Mining in Datenströmen" des folgenden Buches zu lesen:

Jiawei Han, Micheline Kamber. Data Mining --- Konzepte und Techniken, 2. Auflage, Morgan Kaufmann Publishers , 2006.

Es führt einen Algorithmus, wie bekannt Lossy Counting , die häufigen Elemente (Elemente , deren Unterstützung ist oberhalb einem approximiert min_support ) mit beliebiger Genauigkeit.

Nicht genau das, was Sie wollen, aber ich dachte, es könnte helfen.

MS Dousti
quelle

vielleicht können Sie mir auf meine Frage helfen hier

Ben