8 ms·
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 al
by phunge 12y ago
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. You aggregate a larger number by combining 2 at a time.
Fun story, an interviewer at Google once asked me to derive reservoir sampling a long time ago, which I completely wiffed.
- mark-r 12y agoI 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.