Designing Machine Learning Systems: An Iterative Process for Production-Ready Applications

by Chip Huyen

Reservoir sampling is a fascinating algorithm that is especially useful when you have to deal with streaming data, which is usually what you have in production. Imagine you have an incoming stream of tweets and you want to sample a certain number, k, of tweets to do analysis or train a model on. You don’t know how many tweets there are, but you know you can’t fit them all in memory, which means you don’t know in advance the probability at which a tweet should be selected. You want to ensure that: Every tweet has an equal probability of being selected. You can stop the algorithm at any time and the tweets are sampled with the correct probability. One solution for this problem is reservoir sampling. The algorithm involves a reservoir, which can be an array, and consists of three steps: Put the first k elements into the reservoir. For each incoming nth element, generate a random number i such that 1 ≤ i ≤ n. If 1 ≤ i ≤ k: replace the ith element in the reservoir with the nth element. Else, do nothing.