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

Algorithms Every Programmer Should Know: Reservoir Sampling

omniref.com

Post reply on HN
Print view View original

71–80 of 114 posts

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#71

Post by jandrewrogers »

Just looking at the comments, I think their is a tacit assumption on the part of some commenters that a stream of unordered records from a database has a random distribution relative to the value you care about.

That is almost never true. In fact, I have seen clever performance optimizations in database applications that exploit I/O scheduler and layout induced bias in index-less record order. In practice, sampling 25% of very large database tables will often not be representative of sampling 100% of that database table even if the value is not explicitly indexed. Database engines automatically do a lot of low-level optimizations that introduce bias in a nominally random dump of records as a stream.

It is actually quite difficult to randomly sample a large database table.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#72

Post by earino »

The timing of this post is pretty great! I work a lot with "largish files" in R, and while R has gotten much better at reading big files (thanks to data.table's fread), often times you really don't want to work with the whole file. I was surprised that there wasn't a tool to sample from a stream. I wrote a simple perl script https://github.com/earino/fast_sample to do just that. I was "getting around" the issue of needing reservoir sampling by allowing the user to pass in a "proportion of lines" (e.g. .01 for 1%).

I realized that I needed to add the ability to sample an exact number of records, so I went ahead and implemented reservoir sampling. It's a neat algorithm and the performance is pretty stellar. Now I just need to expand it to allow stratified sampling on a column! :)

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#73

Post by colefichter »

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…

I might be misunderstanding something, but this seems much more complex than systematic sampling, which is well understood even in the case where the number of records (read: population size) is unknown (this situation occurs in quality control on an assembly line).

Can anyone comment on why this reservoir method would be a better choice than the old fashioned systematic sample? (which, BTW, only requires the generation of one random number to determine the starting record).

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#74

Post by paragraft »

Had a great opportunity to use this in anger a few months ago. Working on a mapping application, where the map could only handle a few hundred items at a time, but the customer account had tens or hundreds of thousands. And the user could set a realtime filter which would select an unpredictable subset of the larger collection.

QA raised a ticket complaining the subset we were using (just taking the first n items from the collection that matched the filter, collection size was enough that we didn't want to double enumerate or store the whole thing in memory) was unbalanced, eg we were giving the impression that areas of the map that had plenty of items were actually empty.

Switched to reservoir sampling to make sure the subset was a fair representation of the collection, with only one pass and not blowing our memory budget. And everyone you explain it to gets to admire the algorithm.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#75

Post by touristtam »

d23 wrote: post #44

This discussion should actually be about the site omniref, since that's why it was posted. Not to say that's a bad thing, since the site seems cool. Just wanted to point that out.

yeah I never came across that website before (probably because I don't touch ruby) and I was pretty impressed. Thanks for sharing. :)

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#76

Post by loqi »

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.

Intuitively, the reason why it balances out is that while earlier items are more likely to be picked, they're also more likely to get kicked out after being picked.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#77

Post by skybrian »

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?

On the other hand, you're likely to be taking a sample of rows that match a query. It's unlikely that the database already keeps track of the count of how many rows will match an arbitrary query, unless you set it up in advance. So you'd need to load the row ids of the matching rows, then sample from them.

A sufficiently smart database might understand "order by rand() limit n" and do reservoir sampling on row id's behind the scenes. I wouldn't count on it, though.

If you set it up in advance, you could also use reservoir sampling to avoid even storing all the data in the first place, while still saving a random sample.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#78

Post by mark-r »

phunge wrote: post #63

Indeed I've always thought this was a very cool algorithm. I once had to extend it for a distributed setting (think mapreduce) where you can cheaply iterate all records but not sequentially. Instead you have multiple reservoirs, and you can't resample those uniformly since each saw a different number of records. The unbiased way to aggregate 2 reservoirs is to draw a random number from a hypergeometric distribution.…

I was able to derive it on the fly fast enough to make a StackOverflow answer once. I had never heard of or used the technique before, and certainly didn't know what it was called.

I'd probably wiff it in an interview too. For some reason my brain doesn't work as well in an interview setting. Thankfully I haven't had to worry about that too many times.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#80

Post by everyone »

I dont need to know this. I've never used a database in my programming career ever (I'm a game programmer btw) I'm not saying its not interesting and I wouldnt want to familiarise myself with it for purposes of general interest, but not only do I dont need to know this but it would waste valuable headspace at the moment. Theres lots of kinds of programming. We dont all do webapp / internety stuff. Essentially the title of this article is not just hyperbolic, its wrong. There are so many article with '10 things programmer must know' (they are usually all related to internet) If I actually went and learned them all I wouldnt be able to remember how to write a shader or rotate stuff.
Post reply on HN