Also of interest:

"Algorithms Every Data Scientist Should Know: Reservoir Sampling" http://blog.cloudera.com/blog/2013/04/hadoop-stratified-rand...