0

I recently heard of the statistic "87% of the US population can be uniquely identified by a tuple of their zip code, birth date and gender". This is apparently not true, and I was wondering how I would verify it if I had the census data. So imagining I had a 300-millions-line-long unsorted text file containing the gender, zip code and birth date of each person living in the US, what would be the quickest way of knowing what percentage of the population is uniquely identifiable by that tuple?

This should be a matter of identifying what percentage of the entries are duplicated in the dataset, but what would be a good way to go about it? I'm interested in useful algorithms and efficient data structures, and speed is more important than memory consumption as long as the latter is kept to a reasonable level.

  • 4
    Probably inserting all that in a database and compose a query using something like select zipCode, birthDate, gender, count(1) from censusData group by zipCode, birthDate, gender – RMalke Sep 15 '16 at 19:25
  • Yep. That would do it. – Robert Harvey Sep 15 '16 at 19:33
  • It may be worth noting that things like this are time sensitive. What might have been a nearly unique identifier in 1990 is very likely less so in 2000. Due to the pigeonhole principle, as the population grows the bigger your composite key has to get. – candied_orange Sep 16 '16 at 14:46
1

SQL solution

You could load all the demographic data into an SQL database:

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

Unfortunately the file importing statement is not SQL standard (e.g. BULK INSERT for SQLServer, LOAD DATA INFILE for mysql, or use SQL*Loader for Oracle).

The easiest and most efficient way would then be to use aggregate functions with a GROUP BY clause to count number of persons sharing the same values for the grouping columns, and keeping only those with duplicates, using a HAVING clause:

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

Online demo

Sorted file solution

You could als get your census file sorted by zip, birth and gender. Then you could read the data, compare each record read to the previous one, and if the same, and count until these value change for a record.

Pseudocode:

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, 
}

Associative map

A last way, here would be to read each record as it comes, and store the 3 tuple values in a map:

  • store 1 if the tuple was not yet loaded
  • increment existing tuple value if it already exists

In the end, iterate trough the map and process the elements having a count greater than 1. Ok, this one will cost you some memory ;-)

0

Not sure this would fit in memory
pseudo code

you could pack it all into one integer
perfect hash 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 I would use int to save space convert dates to yyyymmdd

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.