Progettazione di sistema di Google Trends?

Question

Sto cercando di capire la progettazione del sistema alla base di Google Trends (o di qualsiasi altra funzione di tendenza su larga scala come Twitter).

Sfide:

• bisogno di elaborare grandi quantità di dati per calcolare tendenza.

• supporto Filtering - dal tempo, regione, categoria ecc

• Hai bisogno di un modo per memorizzare per l'elaborazione archiviazione/offline. Il supporto per il filtro potrebbe richiedere l'archiviazione a più dimensioni.

Questo è ciò che la mia ipotesi è (Io ho zero esperienza pratico di tecnologie di MapReduce/NoSQL)

Ogni tema da utente manterrà insieme di attributi che saranno memorizzati ed eventualmente trattati.

Oltre a mantenere lista di ricerche effettuate da data e ora, regione di ricerca, categoria ecc

Esempio:

Ricerca di Kurt Cobain termine:

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

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

Domanda:

• Come calcolano in modo efficiente la frequenza dei termini di ricerca?

• In altre parole, dato un grande set di dati, come fanno a trovare i 10 articoli più frequenti in modo distribuito in scala?

Answer 1

Beh ... trovare i migliori termini K non è davvero un grosso problema. Una delle idee chiave in questo campo è stata l'idea di "elaborazione del flusso", cioè di eseguire l'operazione in un singolo passaggio dei dati e sacrificare un po 'di accuratezza per ottenere una risposta probabilistica.Quindi, si supponga che si ottiene un flusso di dati come il seguente:

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

Quello che vuoi è gli elementi migliori K. Ingenuamente, si manterrebbe un contatore per ogni oggetto e alla fine si ordinerà per il conteggio di ogni oggetto. Ciò richiede lo spazio O(U) e il tempo O(max(U*log(U), N)), dove U è il numero di elementi unici e N è il numero di elementi nell'elenco.

Nel caso U è piccolo, questo non è davvero un grosso problema. Ma una volta entrato nel dominio dei registri di ricerca con miliardi o trilioni di ricerche univoche, il consumo di spazio inizia a diventare un problema.

Così, la gente ha avuto l'idea di "contare schizzi" (potete leggere di più qui: count min sketch page on wikipedia). Qui si mantiene una tabella di hash A di lunghezza n e creare due hash per ogni articolo:

h1(x) = 0 ... n-1 con probabilità uniforme

h2(x) = 0/1 ognuno con probabilità 0.5

È quindi fai A[h1[x]] += h2[x]. L'osservazione chiave è che dal momento che ciascun valore si azzera casualmente a +/- 1, E[ A[h1[x]] * h2[x] ] = count(x), dove E è il valore previsto dell'espressione e il conteggio è il numero di volte in cui x è apparso nel flusso.

Naturalmente, il problema con questo approccio è che ogni stima ha ancora una grande varianza, ma che può essere gestita mantenendo un ampio set di contatori hash e prendendo il conteggio medio o minimo da ciascun set.

Con questa struttura dati di schizzo, è possibile ottenere una frequenza approssimativa per ogni articolo. Ora, è sufficiente mantenere un elenco di 10 articoli con le stime di frequenza più grandi fino ad ora, e alla fine avrete la vostra lista.

Answer 2

Come funziona esattamente una particolare azienda privata fa è probabile che non a disposizione del pubblico, e come valutare l'efficacia di un tale sistema è a discrezione del progettista (che si tratti di voi o Google o chiunque)

Ma molti degli strumenti e delle ricerche sono disponibili per iniziare. Scopri alcuni degli strumenti Big Data, inclusi molti dei progetti Apache di primo livello, come Storm, che consente l'elaborazione di dati di streaming in tempo reale

Guarda anche alcune delle conferenze Big Data e Web Science come KDD o WSDM, così come carte messo fuori da Google Research

come progettare un sistema del genere è impegnativo senza risposta corretta, ma gli strumenti e le ricerche sono a disposizione per iniziare