3 ms·

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 n

by timr 12y ago

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 is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly. But yes, if your sets are small, you have a lot of options.

deleted 12y ago
[deleted]
- timr 12y ago
  If you have N locations with known addresses and you can select a sample of k from those addresses randomly with uniform probability, then sure, do that. But there are lots of situations where you don't have that: say, you're sampling from a database join, or you're just using a table that has non-contiguous id values (e.g. a table with deletions). Or, in the case of truly "Big Data", you have the data spread over multiple machines. In these cases, you need an approach suitable for when you don't know the size of the stream, you can't load it all into memory and/or you can't select randomly from an address pool.
  - detrino 12y ago
    Sorry, I deleted this comment immediately after posting but you managed to respond to it too quickly, it originally said: >Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set. and I have responded here: https://news.ycombinator.com/item?id=9158903 https://news.ycombinator.com/item?id=9158903
deleted 12y ago
[deleted]
keithgabryelski 12y ago
doesn't your implementation require you to fetch all data into the client process for ruby to iterate over? isn't the movement of such data -- when you have billions of rows simply impossible in reasonable time?
- timr 12y ago
  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)
  - keithgabryelski 12y ago
    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.
    - timr 12y ago
      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.
dthal 12y ago
>>Reservoir sampling is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly. I'm not sure that I buy this...Do you have an example? Still, it is a neat algorithm. And it is a true stream query algorithm, that is, if you have an open-ended stream, it maintains a random sample at all times.
Retric 12y ago
While good in theory, it's often really slow in practice as even small sample sets can trash your cache and it still needs a random number for every element. You can make a better approach using a much longer list, but then the math is far less elegant. EX: Add the first X * N elements to the list. Then remove 1/X of them. Then 1/X of the times add an element to the list until it’s full. Cull 1/X of them and then add new elements (1/X)^2 of the time. Repeat until you run out of elements at which point you cull the list back to X elements. Downside is your generating ~N log N random numbers so scanning the list and then sorting a random set may be faster. If you have an approximate number elements AND want a small percentage of them then randomly generate X * N element list which is then culled to an N element list. Finally, if N happens to be close to the full number of elements you’re better off creating an exclusion list. PS: Reservoir Sampling is only good if your memory constrained, need a constant time algorithm, and generating random numbers is expensive.
deleted 12y ago
[deleted]
eridius 12y ago
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 and doing a lot of array manipulation). Or you could do one query fetching just the primary key, record the keys of the indices you're interested in, and then do a second query to fetch that set. Or maybe SQL does have some way to fetch by index after all.
- dlubarov 12y ago
  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 12y ago
    [deleted]
  - eridius 12y ago
    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)) } Yeah, you're doing a bunch of queries, but you're removing all of copying all the data from all the rows.
    - dbenhur 12y ago
      OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).
      - 12y ago
colefichter 12y ago
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).

by timr 12y ago

deleted 12y ago

[deleted]

timr 12y ago
If you have N locations with known addresses and you can select a sample of k from those addresses randomly with uniform probability, then sure, do that. But there are lots of situations where you don't have that: say, you're sampling from a database join, or you're just using a table that has non-contiguous id values (e.g. a table with deletions). Or, in the case of truly "Big Data", you have the data spread over multiple machines. In these cases, you need an approach suitable for when you don't know the size of the stream, you can't load it all into memory and/or you can't select randomly from an address pool.
- detrino 12y ago
  Sorry, I deleted this comment immediately after posting but you managed to respond to it too quickly, it originally said: >Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set. and I have responded here: https://news.ycombinator.com/item?id=9158903 https://news.ycombinator.com/item?id=9158903

deleted 12y ago

[deleted]

keithgabryelski 12y ago

doesn't your implementation require you to fetch all data into the client process for ruby to iterate over? isn't the movement of such data -- when you have billions of rows simply impossible in reasonable time?

timr 12y ago
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)
- keithgabryelski 12y ago
  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.
  - timr 12y ago
    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.

dthal 12y ago

>>Reservoir sampling is appropriate with more than just a set of unknown size -- you very frequently know the size of a set, but it's still too big to sample directly. I'm not sure that I buy this...Do you have an example? Still, it is a neat algorithm. And it is a true stream query algorithm, that is, if you have an open-ended stream, it maintains a random sample at all times.

Retric 12y ago

While good in theory, it's often really slow in practice as even small sample sets can trash your cache and it still needs a random number for every element. You can make a better approach using a much longer list, but then the math is far less elegant. EX: Add the first X * N elements to the list. Then remove 1/X of them. Then 1/X of the times add an element to the list until it’s full. Cull 1/X of them and then add new elements (1/X)^2 of the time. Repeat until you run out of elements at which point you cull the list back to X elements. Downside is your generating ~N log N random numbers so scanning the list and then sorting a random set may be faster. If you have an approximate number elements AND want a small percentage of them then randomly generate X * N element list which is then culled to an N element list. Finally, if N happens to be close to the full number of elements you’re better off creating an exclusion list. PS: Reservoir Sampling is only good if your memory constrained, need a constant time algorithm, and generating random numbers is expensive.

deleted 12y ago

[deleted]

eridius 12y ago

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 and doing a lot of array manipulation). Or you could do one query fetching just the primary key, record the keys of the indices you're interested in, and then do a second query to fetch that set. Or maybe SQL does have some way to fetch by index after all.

dlubarov 12y ago
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 12y ago
  [deleted]
- eridius 12y ago
  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)) } Yeah, you're doing a bunch of queries, but you're removing all of copying all the data from all the rows.
  - dbenhur 12y ago
    OFFSET j is O(j) in most RDMSes. You made an o(N/2 * k) algorithm given j is a random number in [0,N).
    - 12y ago

colefichter 12y ago

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).