Comments on Gregable.: Reservoir Sampling

Hi Mark, I was wondering, how the approach be if y...

2011-05-04T14:26:08.868-07:00

Hi Mark,
I was wondering, how the approach be if your weight has floating point precisions?

Dan, nice observation. You can definitely do that...

2009-01-09T11:40:00.000-08:00

Dan, nice observation. You can definitely do that if you know that you have at least X elements remaining in the stream.

If you know how many elements are in the entire set in advance, you can just select random indexes into the set and go from there though.

I'm not convinced you can use your trick if you don't know how many elements are remaining. I could be wrong.

It's not necessary to flip a coin to decide whethe...

2009-01-08T09:00:00.000-08:00

It's not necessary to flip a coin to decide whether to keep each element. Rather, you can generate a random number of elements to skip.

Example: say you're sampling 1000 elements out of a billion. Towards the end of the stream, you're sampling with probability 1/1,000,000. Rather than generating a million random numbers to decide whether to keep each element, you can decide which of the next million elements to keep, saving yourself a million random number generations. Getting the distribution right is a bit tricky, but it can be done.

See http://www.cs.umd.edu/~samir/498/vitter.pdf for details.

A friend of mine just pointed me at http://www.sci...

2008-11-11T13:27:00.000-08:00

A friend of mine just pointed me at http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V0F-4HPK8WS-2&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=49898584b0eb78d9fabc012e11e1963f as another good reference on the topic.

You don't actually need 1000 elements (for the bas...

2008-06-25T23:34:00.000-07:00

You don't actually need 1000 elements (for the basic version of the algorithm).
You can always use just one current element, and in each step, keep it with probability N/N+1, or replace it with the next element from your scan, with the probability 1/N+1 (where N == number of already scanned elements). Using induction it's easy to show it gives correct probabilities for each step of the way (assuming the random number generator you use is good).

I don't know if this variation is also called Reservoir Sampling or can be considered another algorithm, but looks conceptially the same as the one you described (I figured it out when trying to efficiently get a random quote from IRC logs, so I don't know if it has a name).

Interesting post. Your weighted selection method r...

2008-06-25T08:39:00.000-07:00

Interesting post. Your weighted selection method reminds me of "remainder stochastic sampling" for weighted selection when using genetic algorithms.

In practice, one problem with reservoir sampling i...

2008-06-25T07:20:00.000-07:00

In practice, one problem with reservoir sampling is that the cost of generating a random number for each element in the stream may greatly outweigh the cost of counting the length of the stream.

Another tiny (yet important) extension is given by...

2008-06-25T06:37:00.000-07:00

Another tiny (yet important) extension is given by Knuth that if you can't put all 1000 samples in memory, you can store the sample in external file as reservior and store the index of them in the memory. Finally sort the index and retrive the samples from reservior. This result is given at TAoCP, Vol 2, page 144, algorithm R. This result can be extended to the distributed sampling you mentioned above. I met this problem as an interview problem at Google.

Great post, I didn't know this had a name, or abou...

2008-06-25T06:17:00.000-07:00

Great post, I didn't know this had a name, or about the weighted version.

For the "batch" version, you say:

The right answer is generating random integers between 0 and N-1, then retrieving the elements at those indices and you have your answer.

That's sampling with replacement; the reservoir sampling algorithm is without replacement. So they're not quite equivalent, but in the case you talked about where the dataset is much bigger than the sample size, they're pretty close.

To reduce the number of steps in the uniform case ...

2008-06-25T04:53:00.000-07:00

To reduce the number of steps in the uniform case (1000 out of i), it could be easier to

- draw a random number R from the interval [1,i] (i > 1000, and assuming we index from 1),

- if R <= 1000, replace element R from your current sample with the new element

Interesting article. It's hard to find good blogs ...

2008-06-25T03:55:00.000-07:00

Interesting article. It's hard to find good blogs on practical algorithms. Thanks!

Great post!

I used a similar technique in a...

2008-06-25T03:48:00.000-07:00

Great post!

I used a similar technique in a paper of mine years ago. We needed a way of converting a stream of examples to a manageable batch and hit upon the same random replacement idea.

I didn't realise it was called reservoir sampling and didn't spend any time doing a proper analysis. Good to see someone has though!