I am trying to estimate number of different unique visitors who visited a given website (online store). There are hundreds of millions of visits to the store and so this task is too difficult to handle by my database. Note that one visitor may have more than one visit so it is not enough to count number of all records, we need to find number of all unique visitors. Even when scaling the data into MapReduce cluster this task turns out to be quite difficult.

I decided to sample the data. Each visitor has a Md5 hash (which is a uniform random hexadecimal number) and so I can select all users whose Md5 hash string finishes with for example '0'. By doing so I am sampling 1 in 16 users (1 hex number = 16 possibilities).

In this way I am limiting number of records and the database now can select number of unique visitors (number of distinct visitor hashes). I can simply multiply this number by 16 to get the estimated total number of unique visitors. I did some tests on a small sample of a real data and it works pretty well.

I am trying to find out what is the minimum sample size to get 95% confidence level that the number I arrived at is correct. Some pages are visited by millions of visitors while other have only few hundreds visits. If I will sample 1/16 users on a page which has only 20 users my estimate may be quite off.

Sample data looks in the following way:

Visitor Hash | Website ID | Timestemp | Irrelevant data
009AB730 | 123 | 11111 | 
009AB730 | 122 | 11112 | 
009AB734 | 122 | 11112 | 
0283AB22 | 122 | 11112 | 
0283AB22 | 122 | 11112 | 
.. repeated 1000 times
0283AB22 | 122 | 11112 | 
0283AB20 | 122 | 11112 | 

After sampling this data based on user hash ending with "0" we get:

 009AB730 | 123 | 11111 | 
 009AB730 | 122 | 11112 | 
 0283AB20 | 122 | 11112 | 

So it is irrelevant how many times a given user visited the website, what matters is whether his Hash/Id finishes with 0. This hash should be uniformly random and so we can assume that 1/16 of users IDs finishes with 0. Moreover it is easier to calculate number of unique IDs in the following smaller sample.

That is why I was wondering what should be my minimum sample to achieve less than 5% error? I found this question but I am not sure if I can use the same calculations? There is no proportion in my problem.

My first take on this problem would be to use the same technique and use the worst case scenario assumption by taking largest margin of error when the proportion is 0.5. Using exactly the same logic: the maximum margin of error at 95% confidence is $m = 0.98 / \sqrt{n}.$ Rearranging gives $n = (0.98/m)^2.$ And so if we want a margin of error of 5% = 0.05, $n = (0.98/0.05)^2 = 384$. Therefore we need 384 unique visitors for each webpage in which we want to estimate the number of unique visitors. Since this is the worst case scenario I hope this logic is not flawed? I am worried that I did not use the sampling 1/16 in this calculation. What if I would look for users whose ID finishes with '00' - I would expect that the minimum sample should be bigger in that case.

  • 3
    $\begingroup$ This question is not quite clear. How do you sample every 100th person exactly without implicitly counting all of them? Since you apparently aren't doing that, what is the sampling method you are using? Without describing how the sampling is actually done, it's hard to provide much guidance. $\endgroup$ – cardinal Jun 30 '11 at 13:38
  • 1
    $\begingroup$ (+1) Much clearer now. Good edit. $\endgroup$ – cardinal Jun 30 '11 at 15:12
  • $\begingroup$ How is an estimate or a confidence interval necessary when the sample = the population/10 and the population = 10 * the sample? $\endgroup$ – rolando2 Jul 2 '11 at 2:45
  • $\begingroup$ Indeed, the population in this example is equal 10*sample. In real life I sample 1 in 256 person. So if the population will have only 400 people I will not get as good estimate as if the population would have 100k people. I am trying to find out here what is the minimum number of people in a sample (and in the way in population) required for a good estimate. $\endgroup$ – Datageek Jul 2 '11 at 10:33
  • $\begingroup$ Your rollback of the previous edits is odd. The current version of the post looks very similar to the first and makes my initial comment relevant again. Are you looking to estimate the number of unique entities in a large sample of entities in which each can be present an arbitrary number of times? $\endgroup$ – cardinal Jul 3 '11 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.