4 ms·

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

by timr 12y ago

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.

detrino 12y ago
You can still use this approach as long as you know the total size upfront, just sort the generated index array and use it to skip elements from your input stream, this will save you from having to generate random numbers for every element.
joe_the_user 12y ago
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?
- defen 12y ago
  Ignore the database part - that's just a single concrete example. More abstractly, say you're receiving a continuous stream of events, and you don't know when it will end, and you want to take n samples from that. For example, maybe you have a web service that is receiving click event logs as a stream, and you want to sample 1000 of those, randomly, without storing every single one as it comes in.
- skybrian 12y ago
  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.
- twic 12y ago
  Once-through sequential processing is a pretty common paradigm for large datasets. That's basically what Hadoop and column stores are about. In fact, i think this is the underlying meme of 'big data' - that it's now plausible and useful to do analysis over all of a large dataset, so you might as well build everything around iterating over the entire table regardless.
azernik 12y ago
Or, even better, if you're sampling from a data set as it's being generated. For example, let's say you want to grab 1,000 random tweets out of the output of Twitter's firehose for the next 2 hours - when you decide whether to keep tweet #1,329, you have no idea how many tweets are going to come in after that one, because they haven't been written yet!

by timr 12y ago

detrino 12y ago

You can still use this approach as long as you know the total size upfront, just sort the generated index array and use it to skip elements from your input stream, this will save you from having to generate random numbers for every element.

joe_the_user 12y ago

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?

defen 12y ago
Ignore the database part - that's just a single concrete example. More abstractly, say you're receiving a continuous stream of events, and you don't know when it will end, and you want to take n samples from that. For example, maybe you have a web service that is receiving click event logs as a stream, and you want to sample 1000 of those, randomly, without storing every single one as it comes in.
skybrian 12y ago
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.
twic 12y ago
Once-through sequential processing is a pretty common paradigm for large datasets. That's basically what Hadoop and column stores are about. In fact, i think this is the underlying meme of 'big data' - that it's now plausible and useful to do analysis over all of a large dataset, so you might as well build everything around iterating over the entire table regardless.

azernik 12y ago

Or, even better, if you're sampling from a data set as it's being generated. For example, let's say you want to grab 1,000 random tweets out of the output of Twitter's firehose for the next 2 hours - when you decide whether to keep tweet #1,329, you have no idea how many tweets are going to come in after that one, because they haven't been written yet!