Also of interest:
"Algorithms Every Data Scientist Should Know: Reservoir Sampling" http://blog.cloudera.com/blog/2013/04/hadoop-stratified-rand...
Algorithms Every Programmer Should Know: Reservoir Sampling
61–70 of 114 posts
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#62I think in any real life scenario I would have an idea about the number of records in my table, or could figure that out very cost effectively. So to follow in OP's example with Rails, I would just do Table.where(id: [array_of_random_ids]), which is going to be extraordinarily more efficient than his batch processing Table.find_all. Something should really only be filed under "Every Programmer Should Know" if it will…
Reservior sampling does have legitimate use in monitoring: to track real-time percentiles (e.g. over the last 15 minutes), without logging everything and re-calculating on each new data entry. I do think it is important and useful to know about it, but probably would not use it for the database sampling (as it was in the article).
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#63Indeed 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.
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#64I used to work on a hospital database, back before the internet. It happened a few times that we were asked for a random sample of records. It was quite common to want to recalculate the rehabilitation rates and other stats. This was a problem, as patient records filled several tapes and, being the youngster, I had to sit loading tapes for hours. Because our data set was bigger than memory, we had trouble deciding wh…
So the hospital was expecting random samples each time, but kept getting the same sample (with some appended records)?
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#65Earlier quoted context omitted.
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…
If you know the size of the set, then you can generate a random set of (non-duplicate) indices, and use those to fetch data. Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers a…
Yeah - unfortunately there isn't a great way to select n random rows in standard SQL.
If you have an integral primary key, you could select its max and generate random numbers up to that. Continuity isn't guaranteed so you would need to check for nonexistent primary keys in addition to checking for duplicates.
If there's no integral primary key, then there's no standard SQL solution faster than O(n).
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#66Earlier quoted context omitted.
This implementation is useful at some scales, but not all: it uses find_each to iterate over the ActiveRecord scope, which is going to be slower than doing it all in the database (if that's possible), but still way better than instantiating every record in a large table. (find_each instantiates a few records at a time, then throws them away)
it will, in general, instantiate N-n/N records (even distribution, right - N=total records, n=sample size) that is still too much data to fetch to the client for any large data set.
You don't have to instantiate the records; that's just the way I did it here. For example, you could do two passes: one to randomly select IDs, and one to fetch a small number of records for the sample set. That's O(2N), but still better than what most databases will do for an ORDER BY RANDOM() query.
There's also another, less-known variant of this algorithm that I'll go into in a future post that alleviates the concern.
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#67Earlier quoted context omitted.
If you know the size of the set, then you can generate a random set of (non-duplicate) indices, and use those to fetch data. Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers a…
Yeah - unfortunately there isn't a great way to select n random rows in standard SQL. If you have an integral primary key, you could select its max and generate random numbers up to that. Continuity isn't guaranteed so you would need to check for nonexistent primary keys in addition to checking for duplicates. If there's no integral primary key, then there's no standard SQL solution faster than O(n).
[deleted]
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#68[deleted]
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#69Earlier quoted context omitted.
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…
If you know the size of the set, then you can generate a random set of (non-duplicate) indices, and use those to fetch data. Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers a…
My first solution would have been getting a count, maybe a cached count and just doing random between 0 and that count, fetching by index?
Or if you want more than one, just get a slice? Probably not the best, but at the top of my head.
Re: Algorithms Every Programmer Should Know: Reservoir Sampling
#70Earlier quoted context omitted.
If you know the size of the set, then you can generate a random set of (non-duplicate) indices, and use those to fetch data. Offhand I'm not sure how to do that in SQL, since data isn't usually fetched by index (unless the row has an explicit index key). Worst-case you could iterate over the rows just as you do with reservoir sampling, and it would still be faster (since you aren't generating tons of random numbers a…
Yeah - unfortunately there isn't a great way to select n random rows in standard SQL. If you have an integral primary key, you could select its max and generate random numbers up to that. Continuity isn't guaranteed so you would need to check for nonexistent primary keys in addition to checking for duplicates. If there's no integral primary key, then there's no standard SQL solution faster than O(n).
If N is sufficiently larger than k, it might actually be faster to do something like
let count = query("SELECT COUNT() FROM table")
let indices = computeIndices(count, k)
for index in indices {
results.append(query("SELECT * FROM table LIMIT 1 OFFSET ?", index))
}