Algorithms Every Programmer Should Know: Reservoir Sampling

Post by timr » Fri, Mar 06, 2015, 7:23 PM UTC

microtonal wrote: post #47

timr wrote: post #43

Earlier quoted context omitted.

You may be right...I spent a lot of time thinking about that, and I convinced myself that this was correct, but I could be wrong. My thinking is that rand(N) in ruby returns a value from [0, N-1] inclusive, which is the complete index range of the sampled stream so far. That sounded right to me. I could be convinced otherwise.

You are not taking the index of the element that you are currently sampling into consideration. Suppose that the sample size is 1 and you are getting the second item (index 1). You will call rand(1), which has 0 as the only possible outcome. So, you will always replace the first item (index 0). Whereas if you would call rand(2) (possible outcomes: 0 and 1), you replace the item in the sample with probability .5 (assu…

Post by c0ldfusion » Fri, Mar 06, 2015, 7:31 PM UTC

javajosh wrote: post #48

microtonal wrote: post #38

Earlier quoted context omitted.

Looping n times, calling rand(n) and putting the random element in the output. This mostly works, and is actually far better, in space and time, Reservoir sampling is normally used on large streams where you do not want to or cannot keep the data you are sampling from in memory.

Then I'm a little bit worried about this algorithm, because if the probability of picking is n/idx then the odds of picking a long tail item get asymptotically close to 0. I'm not sure if it really qualifies as a sample of the entire thing.

Post by eridius » Fri, Mar 06, 2015, 7:38 PM UTC

timr wrote: post #10

eridius wrote: post #5

This algorithm was introduced with the premise > "I have a database table with #{17.kajillion} records, and I want to take a random sample of #{X} of them. How can I do this efficently?" And goes on to say that something like `YourBigTable.all.sample(X)` is bad in time and space. And the link that explains why doing `ORDER BY RANDOM()` is bad lists one reason being that generation of random numbers is relatively expe…

Author here. Yes, reservoir sampling is O(N), but my point there was that it doesn't require instantiating every record at once . Also, the cost of the random number generation isn't the big deal in an ORDER BY RANDOM() implementation -- it's that even the smart implementations end up doing multiple table scans. So even at O(n) this probably beats most implementations of that approach, in practice. Reservoir sampling…

Post by defen » Fri, Mar 06, 2015, 7:46 PM UTC

joe_the_user wrote: post #52

timr wrote: post #42

Earlier quoted context omitted.

As I said on another comment in this thread: if you have the addresses (i.e. database ID values) for all of your records in memory, then sure, sampling directly from that set is faster than iterating over every record in a table. There are lots of cases where this assumption doesn't hold: if you're sampling from a join, or from a table with non-contiguous ID values, for example.

Another way to put it is that reservoir sampling only makes sense if you have to iterate over the entire table regardless. That means, no keys, row numbers or unique values that can chosen at random and found more quickly. It seems less, not more, likely that this kind of situation would exist in a huge table - what use would such a table be if you could only process it sequentially?

Post by willvarfar » Fri, Mar 06, 2015, 7:54 PM UTC