Frage Algorithmus zum Finden der Top 10 Suchbegriffe


Ich bereite mich gerade auf ein Interview vor und es erinnerte mich an eine Frage, die ich in einem früheren Interview einmal gestellt hatte:

"Sie wurden gebeten, eine Software zu entwickeln, die kontinuierlich die Top 10 Suchbegriffe bei Google anzeigt. Sie erhalten Zugriff auf einen Feed, der einen endlosen Echtzeit-Suchstream von Suchbegriffen in Google bietet. Beschreiben Sie, welche Algorithmen und Datenstrukturen du würdest das verwenden, du musst zwei Varianten entwerfen:

(i) Zeigen Sie die Top 10 Suchbegriffe aller Zeiten an (d. h. seit Sie den Feed gelesen haben).

(ii) Zeige nur die Top 10 Suchbegriffe für den letzten Monat, stündlich aktualisiert.

Sie können eine Approximation verwenden, um die Top-10-Liste zu erhalten, aber Sie müssen Ihre Auswahl begründen. "
Ich habe in diesem Interview bombardiert und habe immer noch keine Ahnung, wie ich das umsetzen soll.

Der erste Teil fragt nach den 10 häufigsten Elementen in einer kontinuierlich wachsenden Untersequenz einer unendlichen Liste. Ich habe nach Auswahlalgorithmen gesucht, konnte aber keine Online-Versionen finden, um dieses Problem zu lösen.

Der zweite Teil verwendet eine endliche Liste, aber aufgrund der großen Menge an Daten, die verarbeitet werden, können Sie nicht den gesamten Monat der Suchbegriffe im Speicher speichern und stündlich ein Histogramm berechnen.

Das Problem wird durch die Tatsache erschwert, dass die Liste der Top 10 ständig aktualisiert wird, also müssen Sie Ihre Top 10 irgendwie über ein gleitendes Fenster berechnen.

Irgendwelche Ideen?


110
2017-07-15 22:40


Ursprung


Antworten:


Nun, es sieht nach einer Menge Daten aus, mit möglicherweise sehr hohen Kosten für die Speicherung aller Frequenzen. Wenn die Datenmenge so groß ist dass wir nicht hoffen können, alles zu speichern, betreten wir die Domäne von Datenstrom-Algorithmen.

Nützliches Buch in diesem Bereich: Muthukrishnan - "Datenströme: Algorithmen und Anwendungen"

Eng verwandter Hinweis auf das vorliegende Problem, das ich aus dem Obigen ausgewählt habe: Manku, Motwani - "Ungefähre Frequenzziffer über Datenströme" [pdf]

Übrigens war Motwani, Stanford, (redigieren) ein Autor des sehr wichtigen "Randomisierte Algorithmen" Buch. Das 11. Kapitel dieses Buches beschäftigt sich mit diesem Problem. Bearbeiten: Sorry, schlechte Referenz, dieses spezielle Kapitel hat ein anderes Problem. Nach der Überprüfung empfehle ich stattdessen Abschnitt 5.1.2 von Muthukrishnans Buch, Online verfügbar.

Heh, nette Interviewfrage.


46
2017-07-15 23:35



Überblick über die Häufigkeitsschätzung

Es gibt einige wohlbekannte Algorithmen, die Frequenzschätzungen für einen solchen Strom unter Verwendung einer festen Speichermenge bereitstellen können. Einer ist Häufig, von Misra und Gries (1982). Aus einer Liste von n Gegenstände, es finden alle Gegenstände, die mehr als vorkommen n / k Zeiten, mit k - 1 Zähler. Dies ist eine Verallgemeinerung von Boyer und Moore Mehrheit Algorithmus (Fischer-Salzberg, 1982), wo k ist 2. Manku und Motwani's LossyCounting (2002) und Metwally's Raumsparen (2005) Algorithmen haben ähnliche Platzanforderungen, können aber unter bestimmten Bedingungen genauere Schätzungen liefern.

Es ist wichtig zu beachten, dass diese Algorithmen nur Frequenzschätzungen liefern können. Insbesondere kann die Misra-Gries-Schätzung die tatsächliche Häufigkeit um (n / k) Artikel.

Angenommen, Sie hatten einen Algorithmus, der einen Artikel eindeutig identifizieren kann nur wenn es mehr als 50% der Zeit auftritt. Feed diesen Algorithmus einen Strom von N verschiedene Elemente, und fügen Sie dann ein anderes hinzu N - 1 Kopien eines Gegenstandes, x, Für insgesamt 2N - 1 Artikel. Wenn der Algorithmus dir das sagt x mehr als 50% der Gesamtmenge, muss es im ersten Strom gewesen sein; wenn nicht, x war nicht im Anfangsstrom. Damit der Algorithmus diese Feststellung treffen kann, muss er den ursprünglichen Datenstrom (oder eine Zusammenfassung, die proportional zu seiner Länge ist) speichern! So können wir uns selbst beweisen, dass der Raum, der von solch einem "exakten" Algorithmus benötigt wird, Ω wäre (N).

Stattdessen stellen diese hier beschriebenen Frequenzalgorithmen eine Schätzung bereit, die jedes Element identifiziert, das den Schwellenwert überschreitet, zusammen mit einigen Elementen, die um einen bestimmten Abstand darunter liegen. Zum Beispiel die Mehrheit Algorithmus, der einen einzelnen Zähler verwendet, liefert immer ein Ergebnis; Wenn ein Element 50% des Streams überschreitet, wird es gefunden. Es kann aber auch einen Gegenstand geben, der nur einmal vorkommt. Sie würden es nicht wissen, ohne einen zweiten Durchlauf über die Daten zu machen (indem Sie wiederum einen einzelnen Zähler verwenden, aber nur nach diesem Gegenstand suchen).

Der häufige Algorithmus

Hier ist eine einfache Beschreibung von Misra-Gries ' Häufig Algorithmus. Demaine (2002) und andere haben den Algorithmus optimiert, aber das gibt Ihnen den Grund.

Geben Sie den Schwellenwertanteil an, 1 / k; jedes Element, das mehr als auftritt n / k Zeiten werden gefunden. Erstelle eine leere Karte (wie ein rot-schwarzer Baum); Die Schlüssel werden Suchbegriffe sein, und die Werte werden ein Zähler für diesen Begriff sein.

  1. Sieh dir jedes Element im Stream an.
  2. Wenn der Begriff in der Karte vorhanden ist, erhöhen Sie den zugehörigen Zähler.
  3. Andernfalls, wenn die Karte kleiner ist als k - 1 Einträge, fügen Sie den Begriff der Karte mit einem Zähler von eins hinzu.
  4. Allerdings, wenn die Karte hat k - 1 Einträge bereits dekrementieren den Zähler in jedem Eintrag. Wenn ein Zähler während dieses Prozesses Null erreicht, entfernen Sie ihn aus der Karte.

Beachten Sie, dass Sie eine unendliche Datenmenge mit einer festen Speichermenge verarbeiten können (nur die Karte mit fester Größe). Die erforderliche Speichermenge hängt nur vom interessierenden Schwellenwert ab, und die Größe des Streams spielt keine Rolle.

Zählen von Suchanfragen

In diesem Kontext puffern Sie möglicherweise eine Stunde Suchvorgänge und führen diesen Prozess für die Daten dieser Stunde durch. Wenn Sie einen zweiten Durchlauf über das Suchprotokoll dieser Stunde machen können, können Sie eine genaue Anzahl der Vorkommen der obersten "Kandidaten" erhalten, die im ersten Durchgang identifiziert wurden. Oder vielleicht ist es in Ordnung, einen einzigen Pass zu machen, und alle Kandidaten zu melden, wissend, dass jeder Gegenstand, der da sein sollte, enthalten ist, und alle Extras sind nur Lärm, der in der nächsten Stunde verschwinden wird.

Alle Kandidaten, die wirklich den Schwellenwert überschreiten, werden als Zusammenfassung gespeichert. Halten Sie einen Monat lang diese Zusammenfassungen, und werfen Sie die ältesten in jeder Stunde weg, und Sie hätten eine gute Annäherung an die gebräuchlichsten Suchbegriffe.


52
2017-07-15 23:40



Dies ist eines der Forschungsprojekte, die ich gerade durchlaufe. Die Anforderung ist fast genau wie Ihre und wir haben schöne Algorithmen entwickelt, um das Problem zu lösen.

Die Eingabe

Die Eingabe ist ein endloser Strom von englischen Wörtern oder Phrasen (wir bezeichnen sie als tokens).

Die Ausgabe

  1. Gib die oberen N Token aus, die wir gesehen haben weit (von allen Zeichen, die wir haben gesehen!)
  2. Gib die obersten N Token in a aus historisches Fenster, sagen wir, letzten Tag oder letzte Woche.

Ein Antrag dieser Forschung ist, das heiße Thema oder die Tendenzen des Themas in Twitter oder in Facebook zu finden. Wir haben einen Crawler, der auf der Website krabbelt, der einen Strom von Wörtern generiert, die in das System einfließen. Das System wird dann die Wörter oder Sätze mit der höchsten Frequenz entweder insgesamt oder historisch ausgeben. Stellen Sie sich vor, in den letzten Wochen würde der Begriff "World Cup" oft in Twitter erscheinen. So auch "Paul der Oktopus". :)

String in Ganzzahlen

Das System hat eine Integer-ID für jedes Wort. Obwohl es im Internet fast unendlich viele mögliche Wörter gibt, wird die Möglichkeit, neue Wörter zu finden, immer geringer, wenn man einen großen Satz von Wörtern ansammelt. Wir haben bereits 4 Millionen verschiedene Wörter gefunden und ihnen jeweils eine eindeutige ID zugewiesen. Diese ganze Datenmenge kann als Hash-Tabelle in den Speicher geladen werden und verbraucht ungefähr 300 MB Speicher. (Wir haben eine eigene Hash-Tabelle implementiert. Die Java-Implementierung benötigt einen enormen Speicheraufwand)

Jede Phrase kann dann als ein Array von ganzen Zahlen identifiziert werden.

Dies ist wichtig, weil das Sortieren und Vergleichen von Ganzzahlen ist viel viel schneller als auf Saiten.

Archivdaten

Das System archiviert Archivdaten für jedes Token. Grundsätzlich sind es Paare von (Token, Frequency). Allerdings wäre die Tabelle, in der die Daten gespeichert werden, so groß, dass wir die Tabelle physisch partitionieren müssen. Sobald das Partitionsschema auf Ngrammen des Tokens basiert. Wenn das Token ein einzelnes Wort ist, ist es 1 Gramm. Wenn das Token eine Zwei-Wort-Phrase ist, ist es 2 Gramm. Und das geht weiter. Etwa bei 4 Gramm haben wir 1 Milliarde Datensätze mit einer Tischgröße von etwa 60 GB.

Eingehende Streams verarbeiten

Das System absorbiert eingehende Sätze, bis der Speicher vollständig ausgelastet ist (Ya, wir brauchen einen MemoryManager). Nachdem N Sätze genommen und im Speicher abgelegt wurden, pausiert das System und beginnt, jeden Satz in Wörter und Sätze zu zerlegen. Jedes Token (Wort oder Ausdruck) wird gezählt.

Bei sehr häufigen Token werden sie immer im Speicher gehalten. Bei weniger häufigen Tokens werden sie basierend auf IDs sortiert (denken Sie daran, dass wir den String in ein Array von Ganzzahlen übersetzen) und in eine Datei auf der Festplatte serialisiert.

(Für Ihr Problem, da Sie nur Wörter zählen, können Sie alle Wort-Frequenz-Karten nur im Speicher ablegen. Eine sorgfältig entworfene Datenstruktur würde nur 300 MB Speicher für 4 Millionen verschiedene Wörter verbrauchen. Einige Hinweise: Verwenden Sie ASCII-Zeichen für Strings darstellen), und das ist sehr akzeptabel.

In der Zwischenzeit wird ein weiterer Prozess aktiviert, sobald er eine vom System generierte Disk-Datei gefunden hat, und dann mit dem Zusammenführen beginnt. Da die Datenträgerdatei sortiert ist, würde das Zusammenführen einen ähnlichen Vorgang wie das Zusammenführen von Sortieren erfordern. Auch hier muss einiges an Design berücksichtigt werden, da wir zu viele zufällige Festplattensuchen vermeiden wollen. Die Idee besteht darin, gleichzeitig Lesen (Merge-Prozess) / Schreiben (System-Ausgabe) zu vermeiden und den Merge-Prozess beim Schreiben auf einen anderen Datenträger von einem Datenträger lesen zu lassen. Dies ist vergleichbar mit der Implementierung einer Sperre.

Ende des Tages

Am Ende des Tages wird das System viele häufige Token mit einer Frequenz gespeichert im Speicher haben, und viele andere weniger häufige Token, die in mehreren Disk-Dateien gespeichert sind (und jede Datei wird sortiert).

Das System löscht die In-Memory-Map in eine Disk-Datei (sort it). Das Problem besteht jetzt darin, einen Satz der sortierten Datenträgerdatei zusammenzuführen. Mit einem ähnlichen Prozess erhalten wir am Ende eine sortierte Datei.

Die letzte Aufgabe besteht dann darin, die sortierte Festplattendatei in die Archivdatenbank zu integrieren. Abhängig von der Größe der Archivdatenbank funktioniert der Algorithmus wie folgt, wenn er groß genug ist:

   for each record in sorted disk file
        update archive database by increasing frequency
        if rowcount == 0 then put the record into a list
   end for

   for each record in the list of having rowcount == 0
        insert into archive database
   end for

Die Intuition ist, dass nach einiger Zeit die Anzahl der Einfügungen immer kleiner wird. Mehr und mehr Betrieb wird nur bei der Aktualisierung sein. Und diese Aktualisierung wird nicht durch Index bestraft.

Hoffe, diese ganze Erklärung würde helfen. :)


17
2017-07-16 07:41



Du könntest einen benutzen Hash-tabelle kombiniert mit einem binärer Suchbaum. Implementieren a <search term, count> Wörterbuch, das Ihnen sagt, wie oft nach jedem Suchbegriff gesucht wurde.

Offensichtlich wird die gesamte Hash-Tabelle jede Stunde wiederholt, um die Top 10 zu bekommen sehr Schlecht. Aber das ist Google, von dem wir reden, also kannst du davon ausgehen, dass die Top Ten alle bekommen werden, sagen wir über 10 000 Treffer (es ist wahrscheinlich eine viel größere Zahl). Jedes Mal, wenn die Anzahl der Suchbegriffe 10 000 überschreitet, fügen Sie sie in die BST ein. Dann müssen Sie jede Stunde nur die ersten 10 aus dem BST holen, die relativ wenige Einträge enthalten sollten.

Dies löst das Problem der Top-10-aller-Zeit.


Der wirklich knifflige Teil ist der Umgang mit einem Begriff, der den Platz eines anderen im monatlichen Bericht einnimmt (zum Beispiel könnte "stack overflow" in den letzten zwei Monaten 50 000 Treffer haben, aber nur 10 000 im letzten Monat, während "amazon" 40 haben könnte) 000 für die letzten zwei Monate, aber 30 000 für den letzten Monat. Sie möchten, dass "Amazon" in Ihrem Monatsbericht vor "Stapelüberlauf" kommt. Zu diesem Zweck würde ich für alle wichtigen Suchbegriffe (über 10 000 Suchanfragen) eine 30-Tage-Liste speichern, die angibt, wie oft an jedem Tag nach diesem Begriff gesucht wurde. Die Liste würde wie eine FIFO-Warteschlange funktionieren: Sie entfernen den ersten Tag und fügen jeden Tag (oder jede Stunde) einen neuen ein, aber dann müssen Sie möglicherweise mehr Informationen speichern, was mehr Speicherplatz bedeutet. Wenn Speicher kein Problem ist es, sonst gehen Sie für diese "Annäherung", über die sie sprechen).

Das sieht nach einem guten Start aus. Sie können sich dann Sorgen machen, die Begriffe zu beschneiden, die> 10 000 Treffer haben, aber seit langer Zeit nicht mehr viele und solche Sachen.


4
2017-07-15 23:08



Fall i)

Pflegen Sie eine Hashtabelle für alle Suchlisten sowie eine sortierte Top-Ten-Liste, die von der Hashtabelle getrennt ist. Wenn eine Suche stattfindet, erhöhen Sie das entsprechende Element in der Hashtabelle und prüfen Sie, ob dieses Element jetzt mit dem 10. Element in der Top-Ten-Liste geschaltet werden soll.

O (1) Suche nach der Top-Ten-Liste und maximale O (log (n)) -Einfügung in die Hashtabelle (unter der Annahme, dass Kollisionen von einem selbstbalancierenden Binärbaum verwaltet werden).

Fall ii) Anstatt eine riesige Hashtabelle und eine kleine Liste zu pflegen, pflegen wir eine Hashtabelle und eine sortierte Liste aller Einträge. Wenn eine Suche durchgeführt wird, wird dieser Begriff in der Hashtabelle inkrementiert, und in der sortierten Liste kann der Begriff überprüft werden, um zu sehen, ob er mit dem Begriff danach wechseln soll. Ein selbstbalancierender Binärbaum könnte dafür gut funktionieren, da wir ihn auch schnell abfragen müssen (mehr dazu später).

Zusätzlich pflegen wir eine Liste von 'Stunden' in Form einer FIFO-Liste (Warteschlange). Jedes Stundenelement würde eine Liste aller Suchen enthalten, die innerhalb dieser bestimmten Stunde durchgeführt wurden. So könnte beispielsweise unsere Stundenliste wie folgt aussehen:

Time: 0 hours
      -Search Terms:
          -free stuff: 56
          -funny pics: 321
          -stackoverflow: 1234
Time: 1 hour
      -Search Terms:
          -ebay: 12
          -funny pics: 1
          -stackoverflow: 522
          -BP sucks: 92

Dann jede Stunde: Wenn die Liste mindestens 720 Stunden lang ist (das ist die Anzahl der Stunden in 30 Tagen), sehen Sie sich das erste Element in der Liste an und dekrementieren Sie für jeden Suchbegriff das Element in der Hashtabelle um den entsprechenden Betrag . Löschen Sie anschließend das erste Stundenelement aus der Liste.

Nehmen wir an, wir sind um 7 Uhr und wir sind bereit, die erste Stunde in unserer Liste (oben) zu betrachten. Wir haben Gratissachen um 56 in der Hashtabelle, lustige Bilder um 321 usw. dekrementiert und dann die Stunde 0 komplett aus der Liste entfernt, da wir sie nie wieder sehen müssen.

Der Grund, warum wir eine sortierte Liste aller Begriffe pflegen, die schnelle Abfragen ermöglichen, liegt darin, dass wir jede Stunde, nachdem wir die Suchbegriffe vor 720 Stunden durchgegangen sind, sicherstellen müssen, dass die Top-Ten-Liste sortiert bleibt. Wenn wir zum Beispiel "free stuff" um 56 in der Hashtabelle dekrementieren, prüfen wir, wo es jetzt in der Liste steht. Da es sich um einen sich selbst ausbalancierenden binären Baum handelt, kann all dies in O (log (n)) Zeit erreicht werden.


Edit: Opfergenauigkeit für den Weltraum ...

Es könnte nützlich sein, auch eine große Liste in der ersten zu implementieren, wie in der zweiten. Dann könnten wir die folgende Speicherplatzoptimierung in beiden Fällen anwenden: Führen Sie einen Cron-Job aus, um alle außer dem obersten zu entfernen x Elemente in der Liste. Dies würde den Platzbedarf niedrig halten (und dadurch Abfragen in der Liste schneller machen). Natürlich würde es zu einem ungefähren Ergebnis führen, aber das ist erlaubt. x könnte berechnet werden, bevor die Anwendung basierend auf verfügbarem Speicher bereitgestellt wird, und dynamisch angepasst werden, wenn mehr Speicher verfügbar wird.


3
2017-07-15 23:41



Grobes Denken ...

Für die Top 10 aller Zeiten

  • Verwenden einer Hash-Sammlung, in der eine Zählung für jeden Begriff gespeichert wird (Begriffe sanieren usw.)
  • Ein sortiertes Array, das die laufenden Top 10 enthält, ein Term / Count, der zu diesem Array hinzugefügt wird, wenn der Zählerstand eines Terms gleich oder größer als der kleinste Zähler im Array wird

Für monatlich top 10 aktualisiert stündlich:

  • Unter Verwendung eines Arrays, das nach Anzahl der seit dem Start von Modulo 744 (Anzahl der Stunden während eines Monats) verstrichenen Stunden indiziert ist, enthalten die Array-Einträge eine Hash-Sammlung, in der eine Zählung für jeden in diesem Stunden-Slot gefundenen Term gespeichert ist. Ein Eintrag wird zurückgesetzt, wenn sich der Stundenschlitzzähler ändert
  • Die Statistiken in dem auf dem Stunden-Slot indizierten Array müssen gesammelt werden, wenn sich der aktuelle Stunden-Slot-Zähler ändert (höchstens einmal pro Stunde), indem der Inhalt dieses auf Stunden-Slots indizierten Arrays kopiert und abgeflacht wird

Errr ... Sinn machen? Ich habe das nicht so durchdacht wie im richtigen Leben

Ach ja, vergaß zu erwähnen, dass das stündliche "Kopieren / Abflachen", das für die monatlichen Statistiken erforderlich ist, den gleichen Code wiederverwenden kann, der für die Top 10 aller Zeiten verwendet wurde, ein schöner Nebeneffekt.


2
2017-07-15 23:41



Genaue Lösung

Erstens, eine Lösung, die korrekte Ergebnisse garantiert, aber viel Speicher benötigt (eine große Karte).

"Allzeit" Variante

Pflegen Sie eine Hash-Map mit Abfragen als Schlüssel und deren Anzahl als Werte. Behalten Sie außerdem eine Liste von 10 häufigsten Abfragen und die Anzahl der zehn häufigsten Abfragen (eine Schwelle) bei.

Aktualisieren Sie die Karte ständig, während der Stream der Abfragen gelesen wird. Jedes Mal, wenn eine Zählung den aktuellen Schwellenwert überschreitet, führen Sie die folgenden Schritte aus: Entfernen Sie die 10. Abfrage aus der Liste "Top 10", ersetzen Sie sie durch die gerade aktualisierte Abfrage, und aktualisieren Sie den Schwellenwert ebenfalls.

"Letzter Monat" Variante

Behalte die gleiche "Top 10" -Liste und aktualisiere sie auf die gleiche Weise wie oben. Halten Sie auch eine ähnliche Karte, aber dieses Mal speichern Vektoren von 30 * 24 = 720 zählen (eins für jede Stunde) als Werte. Jede Stunde mache folgendes für jeden Schlüssel: Entferne den ältesten Zähler vom Vektor und füge am Ende einen neuen hinzu (initialisiert auf 0). Entfernen Sie den Schlüssel aus der Karte, wenn der Vektor Null ist. Außerdem müssen Sie jede Stunde die "Top 10" -Liste von Grund auf neu berechnen.

Hinweis: Ja, dieses Mal speichern wir 720 Ganzzahlen statt einer, aber es gibt viel weniger Schlüssel (die Allzeitvariante hat eine Ja wirklich langen Schwanz).

Annäherungen

Diese Näherungswerte garantieren nicht die richtige Lösung, sind aber weniger speicherintensiv.

  1. Verarbeiten Sie jede N-te Abfrage und überspringen Sie den Rest.
  2. (Nur für All-Time-Variante) Halten Sie höchstens M Schlüssel-Wert-Paare in der Karte (M sollte so groß sein, wie Sie sich leisten können). Es ist eine Art LRU-Cache: Jedes Mal, wenn Sie eine Abfrage lesen, die nicht in der Map enthalten ist, entfernen Sie die am längsten nicht verwendete Abfrage mit Count 1 und ersetzen Sie sie durch die aktuell verarbeitete Abfrage.

2
2017-07-16 00:21



Top 10 Suchbegriffe für den letzten Monat

Verwenden von Speicher effiziente Indexierung / Datenstruktur, wie z dicht gepackte Versuche (aus Wikipedia Einträge auf versucht) definiert näherungsweise eine Beziehung zwischen Speicheranforderungen und n - Anzahl von Termen.

Falls der erforderliche Speicher verfügbar ist (Annahme 1), können Sie genaue monatliche Statistiken speichern und jeden Monat in alle Zeitstatistiken zusammenfassen.

Es gibt auch eine Annahme, die den 'letzten Monat' als festes Fenster interpretiert. Aber selbst wenn das Monatsfenster gleitet, zeigt das obige Verfahren das Prinzip (das Gleiten kann mit festen Fenstern gegebener Größe approximiert werden).

Das erinnert mich an Round-Robin-Datenbank mit der Ausnahme, dass einige Statistiken auf 'all time' berechnet werden (in dem Sinne, dass nicht alle Daten beibehalten werden; rrd konsolidiert Zeitperioden ohne Berücksichtigung von Details durch Mittelung, Zusammenfassung oder Auswahl von max / min-Werten, bei gegebener Aufgabe das Detail, das verloren geht) sind Informationen über niederfrequente Elemente, die Fehler verursachen können).

Annahme 1

Wenn wir den ganzen Monat keine perfekten Werte halten können, dann sollten wir in der Lage sein, eine bestimmte Periode P zu finden, für die wir perfekte Werte halten können. Nehmen wir zum Beispiel an, dass wir perfekte Statistiken für eine bestimmte Zeitperiode P haben, die n mal in den Monat geht.
Perfekte Statistiken definieren die Funktion f(search_term) -> search_term_occurance.

Wenn wir alles behalten können n Perfekte Stat-Tabellen im Speicher können dann gleitende Monatsstatistiken wie folgt berechnet werden:

  • Statistiken für den neuesten Zeitraum hinzufügen
  • Entferne Statistiken für die älteste Periode (also müssen wir es behalten) n Perfekte Stat-Tabellen)

Wenn wir jedoch nur die Top 10 auf der aggregierten Ebene (monatlich) behalten, werden wir in der Lage sein, viele Daten aus den vollen Statistiken des festen Zeitraums zu verwerfen. Dies ergibt bereits eine Arbeitsprozedur, die Speicheranforderungen (unter Annahme einer oberen Grenze für die perfekte Stat-Tabelle für die Periode P) festgelegt hat.

Das Problem mit dem obigen Verfahren ist, dass, wenn wir Informationen nur für die Top 10 Begriffe für ein gleitendes Fenster behalten (ähnlich für alle Zeit), dann werden die Statistiken für Suchbegriffe, die in einem Zeitraum ihren Höchststand erreichen, korrekt sein Statistiken für Suchbegriffe, die im Laufe der Zeit ständig eintrudeln.

Dies kann dadurch ausgeglichen werden, dass Informationen zu mehr als 10 Top-Begriffen gespeichert werden, zum Beispiel Top-100-Begriffe, in der Hoffnung, dass die Top 10 korrekt sind.

Ich denke, dass eine weitere Analyse die Mindestanzahl von Vorkommnissen betreffen könnte, die für einen Eintrag erforderlich sind, um Teil der Statistiken zu werden (was mit dem maximalen Fehler zusammenhängt).

(Bei der Entscheidung, welche Einträge Teil der Statistik werden sollen, könnte man auch die Trends beobachten und verfolgen; zum Beispiel, wenn eine lineare Extrapolation der Ereignisse in jeder Periode P für jede Periode Ihnen sagt, dass der Begriff in ein oder zwei Monaten signifikant wird könnte bereits mit dem Tracking beginnen. Ein ähnliches Prinzip gilt für das Entfernen des Suchbegriffs aus dem verfolgten Pool.)

Der schlimmste Fall für das obige ist, wenn Sie viele fast gleich häufig Begriffe haben und sie die ganze Zeit ändern (zum Beispiel wenn Sie nur 100 Begriffe verfolgen, dann wenn Top 150 Begriffe gleich oft vorkommen, aber Top 50 sind häufiger im ersten Monat und damit später oft die Statistik nicht richtig gehalten wird).

Auch könnte es einen anderen Ansatz geben, der nicht in der Speichergröße festgelegt ist (genau genommen ist dies auch nicht der Fall), was eine minimale Signifikanz in Bezug auf die Vorkommen / Periode (Tag, Monat, Jahr, Allzeit) definieren würde, für die er beibehalten werden soll Statistiken. Dies könnte einen maximalen Fehler in jedem der Stats während der Aggregation garantieren (siehe auch Round-Robin).


2
2017-07-16 09:23



Was ist mit einer Anpassung der "Seitenwechsel-Algorithmus" (auch bekannt als "zweite Chance")? Ich kann mir vorstellen, dass es sehr gut funktioniert, wenn die Suchanfragen gleichmäßig verteilt werden (das heißt, die meisten gesuchten Begriffe erscheinen regelmäßig statt 5 Millionen Mal hintereinander und dann nie wieder).

Hier ist eine visuelle Darstellung des Algorithmus: clock page replacement algorithm


2
2017-07-17 10:47



Speichern Sie die Anzahl der Suchbegriffe in einer riesigen Hash-Tabelle, wobei jede neue Suche ein bestimmtes Element um eins erhöht. Verfolgen Sie die Top 20 oder so Suchbegriffe; Wenn das Element an der 11. Stelle inkrementiert wird, prüfen Sie, ob es Positionen mit # 10 * tauschen muss (es ist nicht notwendig, die Top 10 sortiert zu halten; alles, was Sie interessiert, ist die Unterscheidung zwischen dem 10. und 11.).

*Ähnliche Überprüfungen müssen durchgeführt werden, um zu sehen, ob ein neuer Suchbegriff auf Platz 11 steht, also sprudelt dieser Algorithmus auch auf andere Suchbegriffe herunter - also vereinfache ich ein wenig.


0
2017-07-15 22:54