Come rilevare al meglio i dati duplicati in un set di dati di grandi dimensioni

Question

Come rilevare al meglio i dati duplicati in un set di dati di grandi dimensioni

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

0

Recentemente ho sentito delle statistiche " L'87% della popolazione statunitense può essere identificato in modo univoco da un tuple del loro codice postale, data di nascita e sesso ". Questo è apparentemente non vero , e mi chiedevo come avrei verificato se avessi i dati del censimento. Quindi immaginando di avere un file di testo non codificato lungo 300 milioni di righe contenente il genere, il codice di avviamento postale e la data di nascita di ogni persona che vive negli Stati Uniti, quale sarebbe il modo più rapido per sapere quale percentuale della popolazione è identificabile in modo univoco da tuple?

Questo dovrebbe essere un problema di identificare quale percentuale delle voci sono duplicate nel set di dati, ma quale sarebbe un buon modo per farlo? Mi interessano algoritmi utili e strutture dati efficienti, e la velocità è più importante del consumo di memoria purché quest'ultimo sia mantenuto a un livello ragionevole.

data-structures algorithms

posta user2891462 15.09.2016 - 21:14

fonte

2 risposte

Leggi altre domande sui tag data-structures algorithms

Astrazione in Cordova interazione remota con l'applicazione desktop WPF C #

score 1 · Answer 1

Soluzione SQL

Potresti caricare tutti i dati demografici in un database SQL:

CREATE TABLE PERSON(Id integer PRIMARY KEY, zip text, birth date, gender char /*... */);
...

Purtroppo l'istruzione di importazione dei file non è standard SQL (ad esempio BULK INSERT per SQLServer, LOAD DATA INFILE per mysql oppure usa SQL*Loader per Oracle).

Il modo più semplice ed efficiente sarebbe quindi quello di utilizzare le funzioni di aggregazione con una clausola GROUP BY per contare numero di persone che condividono gli stessi valori per le colonne di raggruppamento e mantenendo solo quelli con i duplicati, utilizzando un HAVING clausola:

SELECT zip, birth, gender, count(*) FROM PERSON 
   GROUP BY zip, birth, gender
   HAVING count(*)>1;

Demo online

Soluzione di file ordinati

Puoi anche ordinare il tuo file di censimento per zip, nascita e sesso. Quindi è possibile leggere i dati, confrontare ogni record letto con quello precedente e, se lo stesso, contare fino a quando questo valore non cambia per un record.

Pseudocodice:

lastrecord = {  };
counter = 1; 
while there's a record to read {
    read record 
    if (record.zip == lastrecord.zip 
          and record.birth==lastreacord.birth 
          and record.gender == lastrecord.gender) {
       counter = counter +1; 
    } 
    else {
         if (counter>1)  {    // output the count of duplicates
               write lastrecord.zip, lastrecord.birth, lastrecord.gender, counter
         }  
         counter =1; 
    }      
    lastrecord = record; 
}
if (counter>1)  {    // output the count of duplicates
     write lastrecord.zip, lastrecord.birth, lastrecord.gender, 
}

Mappa associativa

Un ultimo modo, qui sarebbe quello di leggere ogni record come viene, e memorizzare i 3 valori di tupla in una mappa:

memorizza 1 se la tupla non è stata ancora caricata
incrementa il valore della tupla esistente se esiste già

Alla fine, iterate attraverso la mappa ed elaborate gli elementi con un conteggio maggiore di 1. Ok, questo vi costerà un po 'di memoria ;-)

score 0 · Answer 2

Non sono sicuro che ciò si adatterebbe nella memoria
codice pseudo

potresti comprimere tutto in un unico numero
hash perfetto 12345YYYYMMDD0, 12345YYYYMMDD1 Dictionary

   Dictionary<string, int> dic = new ....
   (while zipbirhsex from file.ReadLine)
   {
       if(dic.ContainsKey[zipbirhsex])
          dic.[zipbirhsex]++;
       else 
          dic.Add(zipbirhsex, 1);
   }

   Dictionary<int, int> dic2 = new ...
   foreach(kvp in dic)
   {
       if(dic2.ContainsKey[kvp.Value])
          dic2.[kvp.Value]++;
       else 
          dic2.Add(kvp.Value, 1);
   }

in sql vorrei usare int per risparmiare spazio converte le date in yyyymmdd

CREATE TABLE PERSON(int zip, int date, bit Sex);
insert ...
select zip, date, Sex, count(*) 
from person  
GROUP BY (zip, DATE, SEX)