Systemdesign von Google Trends?

Question

Ich versuche herauszufinden, System-Design hinter Google Trends (oder jede andere solche große Trend-Feature wie Twitter).

Challenges:

• Need große Menge an Daten zu verarbeiten Trend zu berechnen.

• Filtering Unterstützung - von der Zeit, Region, Kategorie usw.

• einen Weg benötigt für die Archivierung/Offline-Bearbeitung zu speichern. Filterunterstützung erfordert möglicherweise mehrdimensionalen Speicher.

Dies ist, was meine Vermutung ist (ich habe Null practial Erfahrung von MapReduce/NoSQL-Technologien)

Jeder Suchbegriff aus Benutzern von Attributen wird maintain eingestellt, und schließlich verarbeitet gespeichert werden.

sowie die Aufrechterhaltung Liste der Suchanfragen durch Zeitstempel, der Region suchen, Kategorie usw.

Beispiel:

für Kurt Cobain Begriff:

Kurt-> (Time stamp, Region of search origin, category ,etc.) 

Cobain-> (Time stamp, Region of search origin, category ,etc.) 

Frage:

• Wie berechnen sie effizient die Häufigkeit des Suchbegriffs?

• Mit anderen Worten, bei einem großen Datensatz, wie finden sie die häufigsten Top 10 Artikel verteilt skalierbar?

Answer 1

zu erhalten begonnen ... Die Top-K-Begriffe zu finden, ist nicht wirklich ein großes Problem. Eine der Schlüsselideen auf diesem Gebiet war die Idee der "Stream-Verarbeitung", d. H. Die Operation in einem einzigen Durchlauf der Daten durchzuführen und einige Genauigkeit zu opfern, um eine probabilistische Antwort zu erhalten.So übernehmen Sie einen Strom von Daten wie folgt erhalten:

A B K A C A B B C D F G A B F H I B A C F I U X A C

Was Sie wollen, ist die Top-K Artikel. Naiv, würde man einen Zähler für jeden Gegenstand behalten und am Ende nach der Zählung jedes Gegenstandes sortieren. Dies dauert O(U) Speicherplatz und O(max(U*log(U), N)) Zeit, wo U ist die Anzahl der einzigartigen Elemente und N ist die Anzahl der Elemente in der Liste.

Wenn U klein ist, ist das nicht wirklich ein großes Problem. Aber sobald Sie in der Domäne von Suchprotokollen mit Milliarden oder Billionen eindeutiger Suchvorgänge sind, wird der Speicherplatzverbrauch zu einem Problem.

Also kamen die Leute auf die Idee von "count-scripts" (mehr können Sie hier lesen: count min sketch page on wikipedia). Hier finden Sie eine Hash-Tabelle A der Länge halten n und schaffen zwei Hashes für jedes Element:

h1(x) = 0 ... n-1 mit einheitlicher Wahrscheinlichkeit

h2(x) = 0/1 jeweils mit einer Wahrscheinlichkeit von 0,5

Sie dann A[h1[x]] += h2[x] tun. Die Schlüsselbeobachtung ist, dass jeder Wert zufällig auf +/- 1, E[ A[h1[x]] * h2[x] ] = count(x) hashed, wobei E der erwartete Wert des Ausdrucks ist und count die Anzahl der Male ist, die x im Stream aufgetreten ist. Das Problem bei diesem Ansatz besteht natürlich darin, dass jede Schätzung immer noch eine große Varianz aufweist, aber dies kann gehandhabt werden, indem eine große Menge von Hash-Zählern verwaltet wird und die durchschnittliche oder minimale Anzahl von jeder Menge genommen wird.

Mit dieser Skizzendatenstruktur können Sie eine ungefähre Häufigkeit für jeden Artikel ermitteln. Jetzt führen Sie einfach eine Liste von 10 Artikeln mit den größten Häufigkeitsschätzungen bis jetzt und am Ende haben Sie Ihre Liste.

Answer 2

Wie genau ein bestimmtes privates Unternehmen tut es nicht öffentlich zugänglich wahrscheinlich ist, und wie die Wirksamkeit eines solchen Systems zu bewerten, im Ermessen des Designers ist (sei es Sie oder Google oder wer auch immer)

Aber viele der Werkzeuge und Forschung sind da draußen, um Sie zu beginnen. Sehen Sie sich einige der Big Data-Tools an, darunter viele der Top-Level-Apache-Projekte, wie Storm, die die Verarbeitung von Streaming-Daten in Echtzeit ermöglicht. Weitere Informationen finden Sie auch auf den Konferenzen Big Data und Web Science.

wie KDD oder WSDM, sowie Papiere von Google Research

löschte wie so zu gestalten, ein System ohne richtige Antwort ist eine Herausforderung, aber die Werkzeuge und Forschung zur Verfügung stehen Sie Well