Reservoir Sampling Algorithm

Reservoir sampling is a family of algorithms for choosing a random sample of a fixed number of items from a stream of items whose total size is not known in advance, drawing the sample in a single pass over the stream and without needing to store more than the sample itself. The algorithm maintains a fixed-size buffer, the reservoir, filled initially by the first items seen; as each further item arrives, it is included in the reservoir with a probability calculated from how many items have been seen so far, replacing a uniformly chosen existing reservoir item if it is selected, a rule constructed so every item seen so far has had an equal chance of ending up in the final sample regardless of when it appeared in the stream or how long the stream turns out to be. The technique was introduced by Fan, Muller and Rezucha in 1962; a later, simpler version commonly called Algorithm R was developed independently by researchers including Alan Waterman, and remains the version most often taught and implemented.