title: How do I get an unbiased random sample from a really huge data set?
body: <p>For an application I'm working on, I need to sample a small set of values from a very large data set, on the order of few hundred taken from about 60 trillion (and growing).</p>
  
  <p>Usually I use the technique of seeing if a uniform random number r (0..1) is less than S/T, where S is the number of sample items I still need, and T is the number of items in the set that I haven't considered yet.</p>
  
  <p>However, with this new data, I don't have time to roll the die for each value; there are too many. Instead, I want to generate a random number of entries to "skip", pick the value at the next position, and repeat. That way I can just roll the die and access the list S times. (S is the size of the sample I want.)</p>
  
  <p>I'm hoping there's a straightforward way to do that and create an unbiased sample, along the lines of the S/T test.</p>
  
  <ul>
  <li><p>To be honest, approximately unbiased would be OK.</p></li>
  <li><p>This is related (more or less a follow-on) to this persons question:</p></li>
  </ul>
  
  <p><a href="https://math.stackexchange.com/questions/350041/simple-random-sample-without-replacement">https://math.stackexchange.com/questions/350041/simple-random-sample-without-replacement</a></p>
  
  <ul>
  <li>One more side question... the person who showed first showed this to me called it the "mailman's algorithm", but I'm not sure if he was pulling my leg. Is that right?</li>
  </ul>