Algorithms For Dummies

  Managing Big Data 

     237

Here is how reservoir sample works: Given a stream of data, containing many ele-

ments, you initialize the reservoir sample with elements taken from the stream 

until the sample is complete. For instance, if the sample contains 1,000 elements, 

a number that usually fits in the computer’s internal memory, you start by pick-

ing  the  first  1,000  stream  elements.  The  number  of  elements  you  want  in  the 

sample is k, and k implies a sample that fits into the computer’s memory. At the 

point when you reserve the first k stream elements, the algorithm starts making 

its selections:

1. 

From the beginning of the stream, the algorithm counts every new element 

that arrives. It tracks the counting using the variable named as n. When the 

algorithm gets into action, the value of n is equivalent to k.

2. 

Now, new elements arrive, and they increment the value of n. A new element 

arriving from the stream has a probability of being inserted into the reservoir 

sample of k/n and probability of not being inserted equal to (1 – k/n).

3. 

The probability is verified for each new element arriving. It’s like a lottery: If the 

probability is verified, the new element is inserted. On the other hand, if it isn’t 

inserted, the new element is discarded. If it’s inserted, the algorithm discards 

an old element in the sample according to some rule (the easiest being to pick 

an old element at random) and replaces it with the new element.

The following code shows a simple example in Python so that you can see this 

algorithm in action. The example relies on a sequence of alphabet letters (pretend 

that they are a data stream) and creates a sample of five elements. (You can find 

this code in the 

A4D; 12; Managing Big Data.ipynb

 file on the Dummies site as 

part of the downloadable code; see the Introduction for details.)

import string

datastream = list(string.ascii_uppercase) 

+ list(

    string.ascii_lowercase)

print(datastream)

FIGURE 12-3: 

An example of 

windowing 

a stream of 

DNA data.

---

238