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

31–40 of 114 posts

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#31

Post by keithgabryelski »

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…

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?

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#32

Post by csl »

MrBuddyCasino wrote: post #19
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…

Thanks for the clarification, thats exactly what I was wondering about. I have two questions: - is it a common problem to have, not knowing the set size? - is it O(N), or rather O(n)? My intuition tells me it depends on whether or not I have to retrieve every record in the set or not, because I/O should still be much more expensive than random number generation.

> is it a common problem to have, not knowing the set size?

Yes. It could be as simple as receiving values from a Python generator (or equivalent mechanism in your favourite language), where you don't know the number of items beforehand (and querying for the length is either impossible or expensive).

In such a cases, using reservoir sampling is an elegant solution, because you're probably in a situation where you'll be iterating through all values anyway.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#33

Post by dthal »

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…

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

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#34

Post by timr »

[deleted] wrote: post #24
timr wrote: post #10

Earlier 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…

[deleted]

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.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#35

Post by barking »

gearoidoc wrote: post #28
gearoidoc wrote: post #21

Earlier quoted context omitted.

Downvoted for a compliment. Way to go HN, way to go.

Awesome. Let's keep this going.

It's just the way that you're signalled not to make these kind of posts. It's not personal even if it feels like it.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#36

Post by Retric »

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…

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.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#37

Post by timr »

keithgabryelski wrote: post #31
timr wrote: post #10

Earlier 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…

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?

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)

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#38

Post by microtonal »

javajosh wrote: post #29

I really like this algorithm, and I think it's instructive to think about a naive solution, and how it differs. 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, especially in the case where "putting the element in the output" is expensive (as is implied by the "kajillions of records" premise). The problem with this solutio…

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.

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#39

Post by [deleted] »

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…

[deleted]

Re: Algorithms Every Programmer Should Know: Reservoir Sampling

#40

Post by cnlwsu »

gearoidoc wrote: post #28
gearoidoc wrote: post #21

Earlier quoted context omitted.

Downvoted for a compliment. Way to go HN, way to go.

Awesome. Let's keep this going.

https://news.ycombinator.com/newsguidelines.html

Resist commenting about being downvoted. It never does any good, and it makes boring reading.

Please don't bait other users by inviting them to downvote you.

Post reply on HN