Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reservoir Sampling

samwho.dev

Post reply on HN
Print view View original

61–70 of 107 posts

Re: Reservoir Sampling

#61

Post by tmoertel »

gregable wrote: post #43

Very well put together. If you are curious about the weighted version, I tried to explain it some here: https://gregable.com/2007/10/reservoir-sampling.html There's also a distributed version, easy with a map reduce. Or the very simple algorithm: generate a random paired for each item in the stream and keep the top N ordered by that random.

Two notes on the weighted version. First, the straightforward implementation of selecting the top N when ranked by POW(RANDOM(), 1.0 / weight) has stability problems when the weights are very large or very small. Second, the resulting sample does not have the same distribution in expectation as the population from which it was drawn. This is especially so when the overall weight is concentrated in a small number of population elements. But such samples are workable approximations in many cases.

I discuss these issues more here: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....

Re: Reservoir Sampling

#62

Post by fiddlerwoaroof »

eru wrote: post #49
samwho wrote: post #42

Earlier quoted context omitted.

I hadn’t considered this, cool to know it works!

Though I think it's only strictly true, if the intervals you sample over are the same. Eg they both sample some messages every second, and the all start their second-long intervals on the same nanosecond (or close enough). I find it easier to reason about reservoir sampling in an alternative formulation: the article talks about flipping a random (biased) coin for each arrival. Instead we can re-interpret reservoir sa…

The second formulation sounds easier to use to adapt to specific use cases too: just bump the priority of a message based on your business rules to make it more likely that interesting events get to your log database.

Re: Reservoir Sampling

#63

Post by svat »

fanf2 wrote: post #47
stygiansonic wrote: post #4

Great article and nice explanation. I believe this describes “Algorithm R” in this paper from Vitter, who was probably the first to describe it: https://www.cs.umd.edu/~samir/498/vitter.pdf

That paper says “Algorithm R (which is a reservoir algorithm due to Alan Waterman)” but it doesn’t have a citation. Vitter’s previous paper https://dl.acm.org/doi/10.1145/358105.893 cites Knuth TAOCP vol 2. Knuth doesn’t have a citation.

Knuth also says that "Algorithm R is due to Alan G. Waterman", on TAOCP vol 2 page 144, just below "Algorithm R (Reservoir sampling)". This blog post seems to be a good history of the algorithm: https://markkm.com/blog/reservoir-sampling/ (it was given by Waterman in a letter to Knuth, as an improvement of Knuth's earlier "reservoir sampling" from the first edition).

> All in all, Algorithm R was known to Knuth and Waterman by 1975, and to a wider audience by 1981, when the second edition of The Art of Computer Programming volume 2 was published.

Re: Reservoir Sampling

#64

Post by petters »

wood_spirit wrote: post #2

I remember this turning up in a google interview back in the day. The interview was really expecting me not to know the algorithm and to flounder about trying to solve the problem from first principles. Was fun to just shortcut things by knowing the answer that time.

This also got me past one interview. I came up with k/n but now I think it's better to just generate a random float in [0, 1] and keep the k largest ones

Re: Reservoir Sampling

#65

Post by tmoertel »

samwho wrote: post #50
eru wrote: post #48

Earlier quoted context omitted.

Very nice post! Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement. That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on…

I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible.

A while ago I tried to create a more self-explanatory implementation:

https://github.com/tmoertel/practice/blob/master/libraries%2...

It is limited to integer weights only to make it easy to verify that the algorithm implements the requested distribution exactly. (See the test file in the same directory.)

Re: Reservoir Sampling

#66

Post by tambourine_man »

samwho wrote: post #3

Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)

Your whole blog seems like a treasure trove. I’m glad I found it, thanks for sharing.

Re: Reservoir Sampling

#67

Post by eru »

tmoertel wrote: post #65
samwho wrote: post #50

Earlier quoted context omitted.

I actually read that post on the alias method just the other day and was blown away. I think I’d like to try making a post on it. Wouldn’t be able to add anything that link hasn’t already said, but I think I can make it more accessible.

A while ago I tried to create a more self-explanatory implementation: https://github.com/tmoertel/practice/blob/master/libraries%2... It is limited to integer weights only to make it easy to verify that the algorithm implements the requested distribution exactly . (See the test file in the same directory.)

You could probably restrict to rational numbers, and still verify? Languages like Python, Haskell, Rust etc have good support for arbitrary length rational numbers.

Each floating point number is also a rational number, and thus you could then restrict again to floating point afterwards.

Re: Reservoir Sampling

#69

Post by skykooler »

dekhn wrote: post #21
hinkley wrote: post #17

This reminds me that I need to spend more time thinking about the algorithm the allies used to count German tanks by serial number. The people in the field estimated about 5x as many tanks as were actually produced but the serial number trick was over 90% accurate.

https://en.wikipedia.org/wiki/German_tank_problem

An interesting corollary of this is that if you only have a single sample, it reduces to indicating that your sample is the median value - i.e. if you see one item with serial number N, you can guess that there were roughly 2N produced.

Re: Reservoir Sampling

#70

Post by eru »

fiddlerwoaroof wrote: post #62
eru wrote: post #49

Earlier quoted context omitted.

Though I think it's only strictly true, if the intervals you sample over are the same. Eg they both sample some messages every second, and the all start their second-long intervals on the same nanosecond (or close enough). I find it easier to reason about reservoir sampling in an alternative formulation: the article talks about flipping a random (biased) coin for each arrival. Instead we can re-interpret reservoir sa…

The second formulation sounds easier to use to adapt to specific use cases too: just bump the priority of a message based on your business rules to make it more likely that interesting events get to your log database.

You could do (category, random priority) and then do lexicographic comparison. That way higher categories always outrank lower categories.

But depending on what you need, you might also just do (random priority + weight * category) or so. Or you just keep separate reservoirs for high importance items and for everything else.

Post reply on HN