# Reservoir Sampling

A simple random sampling strategy to produce a sample without replacement from a stream of data - that is, in one pass: O(N)

Want to sample sinstances - uniformly at random without replacement - from a population size of n records, where n is not known.

Figuring out n would require 2 passes. Reservoir sampling achieves this in 1 pass.

A reservoir **R** here is simply an array of size **s**. Let **D** be data stream of size **n**

Algorithm:

- Store first s elements into R.
- for each element in position k = s+1 to n ,
- accept it with probability s/k
- if accepted, choose a random element from R to replace.

Partial analysis:

Base case is trivial. For the k+1st case, the probability a given element i with position <= k is in R is s/k. The prob. i is replaced is the probability k+1st element is chosen multiplied by i being chosen to be replaced, which is: s/(k+1) * 1/s = 1/(k+1), and prob that i is not replaced is k/k+1.

So any given element's probability of lasting after k+1 rounds is: (chosen in k steps, and not removed in k steps)

= s/k * k/(k+1), which is s/(k+1).

So, when k+1 = n, any element is present with probability **s/n.**

#### Distributing Reservoir Sampling

It is very simple to distribute the reservoir sampling algorithm to n nodes.

Split the data stream into n partitions, one for each node. Apply reservoir sampling with reservoir size s, the final reservoir size, on each of the partitions. Finally, aggregate each reservoir into a final reservoir sample by carrying out reservoir sampling on them.

Lets say you split data of size n into 2 nodes, where each partition is of size n/2. Sub-reservoirs R1 and R2 are each of size s.

Probability that a record will be in sub-reservoir is:

s / (n/2) = 2s/n

The Probability that a record will end up in the final reservoir given it is in a sub-reservoir is: s/(2s) = 1/2.

It follows that the probability any given record will end up in the final reservoir is:

2s/n * 1/2 = **s/n**

## Comments

**Anonymous**

February 04, 2008

PingBack from http://msdnrss.thecoderblogs.com/2008/02/05/reservoir-sampling/**Anonymous**

June 05, 2008

In the June 2008 CTP, PLINQ aggregations are more powerful than they were in the December 2007 CTP. The**Anonymous**

January 08, 2014

The distribution of reservoir sampling is not fair to all of the items. If you want a sample of k = 2 you will only be able to pick an item from each partition which is not alright. There must be a chance for, lets say, the two last items in the list to be picked.