Calcolo delle medie delle righe in un set di dati molto grande

Question

Calcolo delle medie delle righe in un set di dati molto grande

#1 da (4 voti)

4

Abbiamo un sistema di classificazione nel nostro sito Web che consente agli utenti di fornire feedback a 3 diverse domande su un utente.
Attualmente calcoliamo la valutazione utilizzando le medie utilizzando la seguente query sul nostro RDBMS:

SELECT AVG(question_1), AVG(question_2), AVG(question_3)
FROM ratings
WHERE user_id = 1

Questa query non è scalabile anche quando il risultato è memorizzato nella cache (e lo è) poiché alcuni dei nostri utenti hanno milioni di voti.
L'uso di un indice funzionale non è un'opzione perché il nostro RDBMS non li supporta e l'utilizzo di uno rallenterebbe significativamente le scritture.

La soluzione che ho trovato è quella di creare un log di sola append delle medie in un dato intervallo di tempo e unirle periodicamente usando una media ponderata.
Quindi avremmo finito con la seguente struttura dati per utente:

| question1_avg | question2_avg | question3_avg | ratings_count | timestamp  |

| 3.4           | 4.5           | 4.9           | 10000         | 1480429792 |

| 5             | 5             | 5             | 30            | 1480429848 |

Quindi il processo di unione sarà simile a:

(3.4 * 10000 + 5 * 30) / 10030

I record precedenti verranno rimossi e la nuova media verrà aggiunta al registro.
Questo disegno è corretto? Funzionerà su larga scala?
Dove conserverai quel tipo di dati? Un archivio di documenti (come MongoDB), un archivio di valori-chiave (come Redis) o un RDBMS?

Poiché questo concetto è molto simile ai contatori CRDT, ho cercato di trovare un tipo di dati replicati convergenti che ti consente per calcolare le medie ma non sono riuscito a trovarne una. C'è una struttura dati che mi è sfuggita?
C'è un altro algoritmo o tipo di dati che dovrei esaminare?

data-structures algorithms

posta the_drow 29.11.2016 - 15:42

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms

Come faccio a rifattare il controller di visualizzazione massivo Perché progettare per dispositivi mobili e ridimensionare su desktop con query multimediale?

score 4 · Accepted Answer

Quello che puoi fare per ottimizzare questo dipende da quanto precisamente funziona il sistema di valutazione, e che tipo di analisi vuoi fare con i dati. Ma se le valutazioni sono discrete (come una valutazione a 1-5 stelle), possiamo calcolarle in modo efficiente memorizzando i voti accumulati in un istogramma . Cioè, contiamo quante volte è stata scelta ciascuna valutazione:

| Question | r1  | r2  | r3  | r4  | r5  | (avg) |
+----------+-----+-----+-----+-----+-----+-------+
|        1 |  12 |  89 | 127 | 698 |  74 |   3.7 |
|        2 |  39 |  72 | 487 | 278 | 124 |   3.4 |
|        3 |  90 |   9 | 776 |  25 | 100 |   3.0 |

dove la media è calcolata come (1*r1 + 2*r2 + 3*r3 + 4*r4 + 5*r5) / (r1 + r2 + r3 + r4 + r5) , che appare noiosa ma è un'operazione a tempo costante.

Questo è simile all'approccio della media ponderata, ma non accumulerà errori nel tempo.

Probabilmente dovresti comunque memorizzare anche le singole valutazioni, in quanto ciò consente un'ulteriore analisi (ad es. esiste una correlazione tra le domande 1 e 3? Ci sono tendenze nel tempo?). Aggregando i dati in un istogramma, perdiamo tali informazioni.

È perfettamente ragionevole memorizzare sia le singole valutazioni che l'istogramma nello stesso database relazionale. In particolare, ciò ci consentirà di mantenere sincronizzati i voti utilizzando i trigger e / o le stored procedure. All'inserimento, il conteggio appropriato viene semplicemente incrementato. Se dovessimo utilizzare un database separato per le valutazioni aggregate, le applicazioni che scrivono nel database dovrebbero svolgere un lavoro aggiuntivo.

Questa strategia non funzionerà se le valutazioni possibili non sono discrete, o quando il calcolo del rating è più complicato di una media semplice, ad es. se i rating decadono nel tempo.