RESERVOIR AND BOOTSTRAP SAMPLING

by Sharon Raj Tanamchintala

The Terms Reservoir sampling and Bootstrap Sampling are very essential aspects of techniques in machine learning and data analysis

These sampling methods help in processing data in terms of large and small populations, let us go in-depth with the sampling techniques and have a clear understanding

The sampling techniques are :

Reservoir Sampling

Reservoir sampling is an algorithm used to randomly sample k items from a stream of n items so that each item in the stream has an equal probability of being included in the sample.

In simple words, Reservoir sampling techniques break down the large population that has k items into a small stream or cluster of observations known as n

This is an advantageous technique in terms of using a large dataset where we don't know the total size of the data In advance

This can also reduce memory usage as the large data was divided into small clusters so it consumes space in memory

How it works:

1. Initialize the Reservoir:

Start by creating a reservoir of size K and fill it with the first K items from the stream.

2. Process Remaining Items:

For each new item (from k+1 to n), decide whether to include it in the reservoir:

• Generate a random number r between 1 and the current item’s position.
• If r is less than or equal to k, replace a randomly chosen item in the reservoir with the new item.
• After processing the entire stream, the reservoir contains a random sample of k items from the stream

let us consider an example for our best understanding.

let us say we have a stream of 6 items (1,2,3,4,5,6) we have to sample 3 items using reservoir sampling

1. initially, at the starting state, the reservoir has 3 items [1,2,3]
2. now, let us process the remaining 4,5,6 items
3. the current position will be 4 as the reservoir already has 3 items, now a random number will be generated between 1 and 4
4. let us say the random number is 2, which is r≤ 3 so the generated number is replaced within the reservoir randomly
5. now the reservoir is [1,2,4], likewise, we do for the next item gives a random number 5, we don't replace any value because it is greater than the sample value so the reservoir remains the same [1,2,4]

this is how the sampling works in the reservoir sampling technique

Where it is used?

1. Data Stream Processing

2. Big Data and Data Warehousing

3. Machine Learning

4. Data Collection and Research

5. Database Systems

6. Streaming Media and Communication

Get Sharon Raj Tanamchintala’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

7. Financial and Market Analysis

Advantages of reservoir sampling

1. Efficient Sampling from Large Datasets

• Handling Large Streams: Reservoir sampling is ideal for situations where you have a very large dataset or data stream and you cannot store the entire dataset in memory. It allows you to sample a fixed number of items efficiently without needing to know the total number of items in advance.

2. Constant Space Complexity

• Memory Efficiency: The space complexity of reservoir sampling is O(k), where k is the size of the reservoir (the number of items you want to sample). This constant space requirement makes it very memory efficient, regardless of the total size of the data stream.

3. Stream Processing

• Real-Time Sampling: It is well-suited for processing data streams in real-time. As new data arrives, the algorithm can update the reservoir efficiently without requiring access to historical data.

4. Flexibility

• Different Reservoir Sizes: You can easily adjust the size of the reservoir kkk according to the needs of your application. If you need a different sample size, you can modify kkk without altering the underlying algorithmic approach.

5. Scalability

• Scalable to Large Data Volumes: Because the algorithm processes each item only once and uses a constant amount of space, it scales well to very large datasets or streams, making it a practical choice for big data scenarios.

Overall, reservoir sampling is a powerful and efficient technique for random sampling from large or streaming datasets, providing uniform probability and requiring minimal memory.

BOOTSTRAP SAMPLING

Bootstrap sampling is a statistical method used to estimate the distribution of a statistic (such as the mean, variance, or other metrics) by repeatedly resampling from an observed dataset. It’s particularly useful for assessing the variability and uncertainty of a statistic when the underlying distribution is unknown or when the sample size is small.

In bootstrap sampling, you create multiple new datasets (bootstrap samples) by sampling with replacements from the original dataset. Each bootstrap sample is of the same size as the original dataset.

in contrast to reservoir sampling instead of diving large, unknown-size samples into smaller streams, Bootstrap sampling creates another copy of data with the replacement of the original dataset.

so this means that each data point in the original dataset can be selected multiple times in each bootstrap sample.

now, let us take an example and elobrate for our best understanding of the sampling technique

1. let us consider a sample of 5 items [2,4,6,8,10]
2. calculate the average of the sample, for example, the average is 30/5 = 6.
3. assume that the second generated samples are [2,8,6,10,10]
4. now, repeat generating the samples and calculating the average for n time i.e (n number of times) let us say for 1000 times
5. 1. [2,8,6,10,10] = 7.2
   2. [4,10,6,8,2] = 6.0
   3. [6,6,8,4,8] = 6.4
   4. [10,2,4,10,8] = 6.8
   5. [2,10,10,8,6] = 7.2
6. repeat the same for 1000 samples
7. analyze the result, for example, we have to find the 95% confidence
8. sort the data in ascending order, the sorted data is [6.0,6.4,6.8,7.2,7.2]
9. Position for 2.5th Percentile: Position=0.025×(5+1)=0.025×6=0.15 , this is the lowest value in data, this is near to 6.0
10. 97.5th Percentile: Position=0.975×(N+1)
11. Position=0.975×(5+1)=0.975×6=5.85, this is the highest value on the data which means it is near to 7.2

• Lower Bound (2.5th Percentile): Approximately the smallest value: 6.0
• Upper Bound (97.5th Percentile): Approximately the largest value: 7.2

Thus, the approximate 95% confidence interval for the mean, based on this bootstrap sample, would be:

[6.0,7.2]

Advantages of Bootstrap Sampling

1. No Assumptions About Distribution:

• It does not require assumptions about the underlying distribution of the data. This makes it flexible and broadly applicable.

2. Simple to Implement:

• The method is straightforward and computationally feasible, even for complex statistics

3. Confidence Intervals and Variability:

• It provides a way to estimate confidence intervals and the variability of statistics without needing large sample sizes.

4. Application to Small Samples:

• Useful for small samples where traditional parametric methods might not be reliable.

Bootstrap sampling is a powerful and versatile tool in statistics, especially when dealing with real-world data where the underlying distribution is unknown or assumptions are difficult to meet.