Conta i visitatori unici per gruppo di luoghi visitati

Question

Conta i visitatori unici per gruppo di luoghi visitati

#1 da (1 voti)
#2 da (0 voti)
#3 da (0 voti)

2

Sto affrontando il problema di contare i visitatori unici di gruppi di luoghi.

Ecco la situazione:

Ho visitatori che possono visitare luoghi . Ad esempio, possono essere gli utenti di Internet che visitano le pagine Web oi clienti che visitano i ristoranti. Un visitatore può visitare quanti luoghi desidera e un luogo può essere visitato da più visitatori. Un visitatore può venire nello stesso posto più volte.

I luoghi appartengono a gruppi . Un gruppo può ovviamente contenere diversi luoghi e i luoghi possono appartenere a più gruppi.

Dato che, per ogni visitatore, possiamo avere un elenco di luoghi visitati, come posso avere il numero di visitatori unici per gruppo di posti?

Esempio: ho visitatori A, B, C e D; e ho posti x, y e z.

Ho questi elenchi di visite:

[
 A -> [x,x,y,x],
 B -> [],
 C -> [z,z],
 D -> [y,x,x,z]
]

Avere questo numero di visitatori unici per posizione è abbastanza semplice:

[
 x -> 2, // A and D visited x
 y -> 2, // A and D visited y
 z -> 2  // C and D visited z
]

Ma se ho questi gruppi:

[
 G1 -> [x,y,z],
 G2 -> [x,z],
 G3 -> [x,y]
]

Come posso avere queste informazioni?

[
 G1 -> 3, // A, C and D visited x or y or z
 G2 -> 3, // A, C and D visited x or z
 G3 -> 2  // A and D visited x or y
]

Note aggiuntive:

Ci sono così tanti posti che non è possibile memorizzare informazioni su tutti i possibili gruppi;
Non è un problema se viene fatta l'approssimazione. Non ho bisogno di precisione al 100%. Avere un algoritmo veloce che mi dice che c'erano 12345 visite in un gruppo anziché 12543 è meglio di un lento algoritmo che indica il numero esatto. Diciamo che può esserci una deviazione di ~ 5%.
Ho un numero finito di visitatori e un numero finito di posti. Non ho così tanti posti (circa 60 per ora, ma può arrivare a 200) ma ho molti visitatori (stimati a 50 milioni e questo numero potrebbe crescere fino a 200 milioni nei prossimi mesi).

Esiste un algoritmo o una classe di algoritmi che risolve questo tipo di problema?

algorithms statistics count

posta Mathieu 12.06.2014 - 16:37

fonte

3 risposte

Leggi altre domande sui tag algorithms statistics count

Come definire nomi diversi per lo stesso tipo e farli controllare dal compilatore? [duplicare] In che modo gli spazi tabella differiscono in DB2 dai database in MySQL o MS SQL Server? [chiuso]

score 1 · Answer 1

Sto rispondendo alla mia stessa domanda perché penso di aver trovato un modo per evitare di immagazzinare enormi quantità di dati. Ovviamente implica un'approssimazione ma, come ho detto, non è importante avere il numero esatto di visitatori unici.

Ciò di cui ho bisogno è una tabella che mappa, per ogni luogo, il numero totale di visite. Quindi, seguendo l'esempio che ho dato nella domanda, avrei questo:

[
 x -> 5,
 y -> 2,
 z -> 3
]

Quindi, memorizzo un contatore del numero totale di visitatori unici, che è 3 (e non 4 perché B non ha visitato nulla).

Memorizzo anche il numero totale di visite: 10.

Per conoscere il numero (approssimativo) di visitatori unici, eseguo una moltiplicazione incrociata. Computo il loro numero totale di visite e divido quel numero per il numero totale di visite. Moltiplico il risultato per il numero totale di visitatori unici.

È equivalente a dire: "Se un gruppo fa una proporzione p delle visite, suppongo che abbia anche la stessa proporzione di visitatori unici".

Prendiamo i gruppi dalla domanda:

[
 G1 -> [x,y,z],
 G2 -> [x,z],
 G3 -> [x,y]
]

Possiamo ottenere il loro numero (approssimativo) di visitatori unici come questo:

[
 G1 -> ((5+2+3)/10) * 3 = 3
 G2 -> ((5+3)/10) * 3 = 2.4
 G3 -> ((5+2)/10) * 3 = 2.1
]

I numeri [3, 2.4, 2.1] non sono molto lontani dal risultato reale [3, 3, 2] .

Ciò che possiamo dire è questo:

Per il caso speciale del gruppo che contiene tutti i posti, il risultato restituito non è un'approssimazione, è esatto.
In altri casi, funziona bene se tutti i visitatori hanno lo stesso comportamento di visita. Ad esempio, alcuni visitatori che visitano molti luoghi solo una volta e alcuni visitatori che visitano solo un posto molte volte non daranno buoni risultati.
Il caso peggiore sarebbe che, in un primo gruppo, tutti i posti abbiano pochi visitatori diversi che vengono più volte e, in un secondo gruppo, ci sarebbero molti visitatori diversi che vengono solo una volta. Il numero di visitatori unici del primo gruppo sarebbe sopravvalutato mentre sarebbe sottovalutato per il secondo gruppo.

score 0 · Answer 2

Sembra che tu abbia visitatori finiti e luoghi finiti da visitare solo in più combinazioni. Se è così, allora puoi sapere chi ha visitato. Come? Raccomando di utilizzare una coda per ogni luogo da visitare.

Quando i visitatori visitano, li accoda (posizionali nella coda). Se i visitatori visitano più volte, saranno in coda più volte.

Dato che sei interessato solo a sapere se i visitatori hanno visitato, esegui un dequio (rimuovilo dalla coda) e registra chi ha visitato.

Con questo metodo, dovresti essere in grado di registrare con precisione chi ha visitato cosa, quante volte e in quale ordine.

score 0 · Answer 3

Come hai sottolineato, la memorizzazione del numero di visitatori per ogni permutazione possibile sarebbe una massiccia quantità di dati, o almeno una tabella nel tuo database con un numero enorme di record.
Tuttavia, non c'è davvero alcun modo per aggirarlo, lo si dovrà archiviare, altrimenti come si può ricordare quale sia stato il conteggio precedente per aumentarlo?
Quindi, quello che fai è memorizzare solo quelle permutazioni e il loro conteggio dove effettivamente ci sono stati visitatori (la mia ipotesi sarebbe che sarebbe molto meno del numero totale possibile di permutazioni, per esempio se stai contando i visitatori del tuo negozio in tutto il mondo, molte persone visiteranno i pochi negozi nella loro area generale ma mai quelli dall'altra parte del mondo.

Trova un modo per codificare il set attuale in modo univoco (ad esempio come un hash di sorta), quindi utilizzalo come chiave in una tabella di database.
Quando hai determinato l'hash per una persona, cerca l'hash nella tabella dei conteggi dei visitatori. Se esiste, aumentare il conteggio. Se non esiste, inserire un nuovo record con count = 1.
Un'altra tabella può quindi contenere tale hash in relazione alle tue posizioni, in modo da poter recuperare le posizioni appartenenti a ciascun hash per scopi di reporting. Dì una semplice tabella [location_id, hash] in cui la combinazione è la chiave primaria, entrambe essendo esse stesse chiavi esterne nella tabella delle posizioni e nella tabella dei conteggi rispettivamente. (e quei record possono essere inseriti anche quando si inserisce un nuovo record nella tabella dei conteggi)

Ciò significa che gli inserimenti iniziali sono relativamente lenti, gli aggiornamenti sono veloci quanto stanno per arrivare, e così anche il recupero. Il che, per un ampio potenziale di dati da cui utilizzerai solo un sottoinsieme relativamente piccolo, è il meglio che puoi sperare.