Reservoir Sampling Algorithm In C++

Sampling is a crucial aspect in the fields of data science and statistics as it enables the extraction of a smaller subset from a larger population. An effective technique for this purpose is reservoir sampling, where a specific number of items (k) are chosen from a dataset or stream with a size of (n).

This tutorial provides a summary of the reservoir sampling technique and illustrates how it can be coded in C++. Reservoir sampling is particularly useful for selecting a sample from a large dataset that cannot be stored completely in memory. It keeps a constant-sized reservoir while going through each element in the stream one by one.

We are going to explore the reasoning. The idea behind reservoir sampling before presenting a code excerpt that demonstrates its application in C++. The provided code will address tasks like setting up the reservoir, randomly substituting elements, and presenting the result. This showcase highlights how the reservoir maintains a representative sample as additional data points are ingested from the data stream.

Understanding reservoir sampling is crucial in fields such as analytics, experimentation, personalized suggestions, and efficient management of extensive real-world data sets.

The C++ demonstration illustrates the application of the algorithm in a versatile programming language. To begin, let's delve into the concept of reservoir sampling.

What is Reservoir Sampling Algorithm?

Reservoir sampling is designed to pick k items from a set of n items, where n may not be known in advance. This method allows you to obtain a representative sample of k items from a large dataset by traversing the data only once.

The key ideas behind reservoir sampling are:

• ✅ Maintain a reservoir of size k to store the random sample
• ✅ Fill the reservoir with the first k items from the data stream
• ✅ For subsequent items, randomly replace an item in the reservoir with the new item with probability k/i, where i is the index of the new item.

This results in each item having an equal chance of k/n being selected for the reservoir, ensuring a uniform random sample is obtained.

The algorithm works as follows:

• ✅ Initialize a reservoir array of size k to store the random sample
• ✅ Insert the first k items from the stream into the reservoir array
• ✅ For item i, where i > k: Generate a random number between 0 and 1 If random number < k/i, replace a random element in the reservoir with item i Otherwise, ignore item i
• ✅ After processing all n items, the reservoir array contains the k randomly chosen items.
• ✅ Generate a random number between 0 and 1
• ✅ If random number < k/i, replace a random element in the reservoir with item i
• ✅ Otherwise, ignore item i

The likelihood of k/i diminishes as i grows, resulting in a reduced chance for each item to substitute an existing one in the reservoir. This ensures that every item has an equal chance of being chosen, thereby keeping the reservoir's sample uniformly distributed as more items are handled.

The reservoir sampling technique is highly effective and operates with a time complexity of O(n) when handling n elements using a reservoir of fixed size k. This method traverses the data just once, making it particularly valuable for handling extensive data streams that exceed memory capacity.

Applications and where is it used

• ✅ Dealing with large data streams: Reservoir sampling is useful when you must sample from a massive data stream that cannot fit entirely in memory. It only requires a fixed-size reservoir and processes items sequentially.
• ✅ Unknown data size: The algorithm works even if the number of items n is unknown beforehand. It maintains the uniform random sample in the reservoir regardless of n.
• ✅ Obtaining representative samples: The reservoir contains a random subset statistically representative of the larger population. It is useful for downstream analysis.
• ✅ A/B testing: Reservoir sampling allows users to be divided into uniform random samples for controlled experiments. For example, testing new features on a sample of users.
• ✅ Recommendation systems: By uniformly sampling users, items, or product ratings, the recommendation model can be trained on an unbiased sample to recommend content.
• ✅ Machine learning: Training ML models on a random subset of data points reduces bias and leads to better model generalization.
• ✅ Data analytics: Analyzing a random sample facilitates computing statistics or visualizations that correctly reflect the complete data distribution.
• ✅ Time series sampling: The reservoir algorithm can sample fixed intervals from streams like server logs, stock ticker data, or sensor readings over time.

Reservoir sampling offers a method to extract a representative subset from a constantly flowing large dataset. This technique is valuable for statistical sampling and examination of extensive real-world data across various fields.

Example:

Implement the Reservoir Sampling algorithm in C++ to randomly pick k elements from a stream of unknown size n.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int k = 5; // reservoir size
int reservoir[k]; 

void reservoirSampling(int stream[], int n) {
  srand(time(NULL));
  
  // insert first k items into reservoir[]
  for(int i = 0; i < k; i++) {
    reservoir[i] = stream[i];  
  }

  //Replace items with gradually decreasing probability
  for(int i = k; i < n; i++) {
    int j = rand() % (i+1); 
    if(j < k) {
      reservoir[j] = stream[i];
    }
  }
}

int main() {
  int stream[] = {10, 2, 43, 55, 9, 21, 61, 8, 12};
  int n = sizeof(stream)/sizeof(stream[0]);
  
  reservoirSampling(stream, n);
  
  cout << "Random k = " << k << " items out of stream are: ";
  for(int i = 0; i < k; i++) {
    cout << reservoir[i] << " "; 
  }
  
  return 0;
}

Output:

Random k = 5 items out of stream are: 55 9 61 8 12

The primary idea is to randomly exchange elements within the reservoir array, with a decreasing probability as more elements are examined from the stream. This strategy guarantees that items at the later positions also have an opportunity to be chosen, similar to the ones at the initial positions.

Explanation:

1. Import the required dependencies. Define constant values to be used throughout the program;

Include cstdlib for rand and srand

Use ctime to seed srand

Define k as the reservoir size

1. Create an array of size k to hold items
2. Develop the reservoirSampling function that takes the stream and size n as parameters
3. Initialize the number generator using the time
4. Directly add the k items to the reservoir array

It sets up the reservoir with k items

1. Begin a loop from k to n 1 to handle the remaining stream items
2. Generate a number j between 0. I, where i ranges from k to n 1
3. If j falls between 0 and k 1, replace the item at index j in the reservoir with the item

This procedure involves randomly exchanging an existing element with a decreasing probability

The probability of selecting an item from the reservoir array is calculated as k divided by i plus one.

Retrieve and display the k elements from the reservoir array.

We begin by initializing the reservoir array with the k elements. Subsequently, as we iterate through the stream from k to n 1, we randomly exchange elements in the array with items. This methodology ensures that we attain a random selection with replacement.

Conclusion:

The Reservoir Sampling technique allows for the random selection of k items from a continuous data stream, even without prior knowledge of the total number of items. This method efficiently addresses the challenge with a time complexity of O(n) and a space complexity of O(k).

Key points in the C++ implementation;

• ✅ It starts by filling a fixed-size reservoir array with the k stream items, introducing random data into the reservoir.
• ✅ The main strategy involves using a replacement approach with decreasing probabilities from k/n to k/(n+1) as more stream items are scanned. It ensures that all items are uniformly and randomly selected for inclusion in the reservoir.
• ✅ The functions rand and srand from cstdlib are utilized to generate numbers for the selection strategy. Srand is initialized with the time to produce outputs in each run.
• ✅ The code is straightforward, well-crafted, and accurately captures the essence of Reservoir Sampling. It produces samples even without knowledge of the total population count.
• ✅ In essence, this C++ implementation uses built-in functions, linear time complexity, constant space complexity, probabilistic selection techniques, and simple logic to effectively create a subset of samples from a sized data stream. It serves as a reference for implementing Reservoir Sampling in applications.
• ✅ The method of reservoir sampling finds uses in scenarios involving data streaming and randomization. For instance, it can be applied to analyze sensor data, monitor search trends on a search engine, simulate financial data flows, randomly pick packets for network monitoring and more.