Reservoir sampling is a family of randomized online algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory. The population is revealed to the algorithm over time, and the algorithm cannot look back at previous items. At any point, the current state of the algorithm must permit extraction of a simple random sample without replacement of size k over the part of the population seen so far.
Example Consider the case when we want to maintain a sample of one item. A simple algorithm is to store the first item with probability 1 {\displaystyle 1} and the k {\displaystyle k} -th item with probability 1 k {\displaystyle {\frac {1}{k}}} . We want to show that the sample is uniformly distributed over all of the items that we have seen at each step since. The proof is by induction on the number of items n {\displaystyle n} . If there is 1 item we always choose it and we are done. If there are already n {\displaystyle n} items, then the probability of one of the items already in the store remaining the store becomes n n + 1 × 1 n = 1 n + 1 {\displaystyle {\frac {n}{n+1}}\times {\frac {1}{n}}={\frac {1}{n+1}}} so the probability of any of the n + 1 {\displaystyle n+1} items remaining in the sample is now 1 n + 1 . {\displaystyle {\frac {1}{n+1}}.} The proof of correctness for the general algorithm where we have an arbitrary number of slots is an extension of this argument.
History and Algorithm R Reservoir sampling was introduced as early as 1962 by Fan, Muller, and Rezucha, who described a sampling algorithm which did not need to know the population size n in advance. A simpler algorithm, known as Algorithm R, was discovered independently by Alan G. Waterman and McLeod & Bellhouse; it can also be viewed as a variant of the Fisher–Yates shuffle. Algorithm R works as follows.
Initialize an array R {\displaystyle R} indexed from 1 {\displaystyle 1} to k {\displaystyle k} , containing the first k items of the input x 1 , . . . , x k {\displaystyle x_{1},...,x_{k}} . This is the reservoir. For each new input x i {\displaystyle x_{i}} , generate a random number j uniformly in { 1 , . . . , i } {\displaystyle \{1,...,i\}} . If j ∈ { 1 , . . . , k } {\displaystyle j\in \{1,...,k\}} , then set R [ j ] := x i . {\displaystyle R[j]:=x_{i}.} Otherwise, discard x i {\displaystyle x_{i}} . Return R {\displaystyle R} after all inputs are processed.
Optimizing running time by skipping elements The Algorithm R described in the previous section has linear runtime, since it generates a random number for every element in the input stream to determine whether it should be included in the reservoir. It was observed by Jeffrey Vitter that it is possible to obtain faster algorithms with sublinear runtime when the algorithm is allowed to skip past sections of the input stream without examining them. Vitter gave a reservoir sampling algorithm which runs in time O ( k ( 1 + log ( n / k ) ) {\displaystyle O(k(1+\log(n/k))} , and proved that this is optimal. Kim-Hung Li described a simple algorithm, Algorithm L, achieving the same asymptotic runtime, and which is described in this section. The starting point for Algorithm L is the observation that if n {\displaystyle n} random numbers u 1 , . . . , u n ∼ U [ 0 , 1 ] {\displaystyle u_{1},...,u_{n}\sim U[0,1]} are generated uniformly and independently, then the indices of the smallest k {\displaystyle k} of them form a uniform sample of the k {\displaystyle k} -subsets of { 1 , . . . , n } {\displaystyle \{1,...,n\}} .
… excerpt ends here. Continue reading the full article.
