Skip to content
Random Sampling with a Reservoir 3 min

Jeffrey Scott Vitter · ACM Transactions on Mathematical Software 1985

Random Sampling with a Reservoir

Vitter's 1985 paper on picking a fair random sample from a stream of unknown length, in one pass and constant space. Watch the reservoir change.

Read the original paper

Algorithms · Yellow Belt · Pro · 3 min read

Random Sampling with a Reservoir

How do you pick a fair random sample from a list when you do not know how long the list is? If you know the length, it is easy: pick random positions. But what if the data is a live stream of events, or a log file too big to count first, or a feed that never ends?

The answer is a small trick known as reservoir sampling. Jeffrey Vitter's 1985 paper studies it carefully and makes it fast. The paper describes sampling when the number of records is unknown beforehand, such as records on a magnetic tape of indeterminate length. Today the same trick is used on logs, events and metrics.

Keep a reservoir of k items. Put the first k items in. Then, for item number t, keep it with probability k / t, replacing a random item in the reservoir. When the stream ends, the reservoir is a uniform random sample of everything seen. It uses constant space and one pass.

The simple rule

The basic method is called Algorithm R in the paper, credited to Alan Waterman. It needs only a handful of lines.

  1. Copy the first k items into the reservoir.
  2. For every later item, number t: pick a random number between 0 and 1.
  3. If it is below k / t, keep the item and let it replace one of the k reservoir items, chosen at random.
  4. Otherwise skip it. When the stream ends, the reservoir is the sample.
The reservoir holds k items. The first k items fill it. Each later item is kept with a probability that shrinks as the stream gets longer, and a kept item kicks out a random current member.

The chance of keeping a new item shrinks as the stream grows. Item 100 is kept with chance k / 100, while item 1,000,000 is kept with chance k / 1,000,000. That makes sense. A longer stream means each item should have a smaller share of the limited room.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Why it is fair
  • Making it fast

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.