12 ms·

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

• 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).
• gearoidoc 12y ago
  Nicely put, sir/ma'am!
  • gearoidoc 12y ago
    Downvoted for a compliment. Way to go HN, way to go.
    • gearoidoc 12y ago
      Awesome. Let's keep this going.
      • barking 12y ago
        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.
      • cnlwsu 12y ago
        https://news.ycombinator.com/newsguidelines.html 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.
    • kbenson 12y ago
      You didn't add anything to the conversation. It's fine to compliment someone, but add to the conversation otherwise the comment is just noise. If all you have to say is that, just upvote.
• edc117 12y ago
  Do you have to make sure to address the scenario where a generated index may possibly not exist in a table (deletion, whatever)? It says nothing about the index being contiguous. This can potentially end up with your algorithm returning less than #{X} if your generated indices don't exist.
  • gearoidoc 12y ago
    You still have to loop over your returned records to verify uniqueness so wouldn't this automatically be solved?
  • Veedrac 12y ago
    Just re-sample the ones that "miss". It won't affect the distribution.
• MrBuddyCasino 12y ago
  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.
  • bo1024 12y ago
    > - is it a common problem to have, not knowing the set size? One motivating case is when the items arrive over time, like you have a website and you want to sample uniformly from your visitors over the course of the next hour. You don't need to know how many people will arrive.
  • csl 12y ago
    > 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.
  • bradleyjg 12y ago
    Imagine you are writing software to sit on a router to: 1) collect data for some length of time, and 2) thereafter have available for querying the (maybe approximate) 25th, 50th, 95th, and 99th percentile TCP connection bandwidth thresholds, and 3) signal when a connection grows beyond the 95th percentile. You only have a fairly limited amount of memory.
    • x0x0 12y ago
      While it's great for medians, reservoir sampling for calculating high or low percentiles, particularly with high dynamic range data, will probably have very high error.
• detrino 12y ago
  > But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. I had the same thought reading this. This solution is only really suitable if the number of elements to select is within some constant of the total number of elements. > More generally, reservoir sampling is appropriate when you don't know the size of the set beforehand. But in the premise, we do know the size of the set. And if you know the size of the set (and have some way to address arbitrary elements), then randomly generating a set of X indices is going to be much simpler and faster. Yeah, you have to deal with duplicate indices, but that's an easy problem to solve. Last time I had to solve this, I came up with the following solution[1] which doesn't generate any duplicates and runs in O(k) where k is the size of result set. [1] http://ideone.com/CAwuxW http://ideone.com/CAwuxW
  • 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?
• cperciva 12y ago
  one reason being that generation of random numbers is relatively expensive Say again? My laptop can read from /dev/urandom at over 1 Gbps. If you're running in userland on modern hardware you can easily hit 10 Gbps. Seeding is hard, but once you've done that, generating random numbers is insanely cheap.
  • eridius 12y ago
    Yeah, I dunno why it says generating random numbers is expensive. I was just quoting his linked source.
  • jamiesonbecker 12y ago
    > Seeding is hard, but once you've done that, generating random numbers is insanely cheap. Depends on your use case. Generating random numbers is indeed relatively expensive: $ time dd if=/dev/zero of=/dev/null bs=1024 count=1M 1073741824 bytes (1.1 GB) copied, 0.348118 s, 3.1 GB/s real 0m0.350s user 0m0.092s sys 0m0.260s $ time dd if=/dev/urandom of=/dev/null bs=1024 count=1M 1073741824 bytes (1.1 GB) copied, 102.332 s, 10.5 MB/s real 1m42.334s user 0m0.152s sys 1m41.994s (I7, 3.2.0-4-amd64)
    • IgorPartola 12y ago
      You are comparing doing nearly nothing vs an PRNG. Presumably, you would spend your computation cycles doing something more useful than generating zeros, at which point I am not certain the difference would be quite so drastic.
    • cperciva 12y ago
      Your /dev/urandom is astonishingly slow. Is this normal for Linux?
      • SamReidHughes 12y ago
        Yes. For example, if you choose the encrypted hard drive option when installing Debian, it'll take forever, like, hours and hours, two digit numbers of hours, because it's reading from some /dev/urandom (I presume) to initialize the drive with random data. You can skip that step though. It's way better to do it beforehand using some script that uses something other than /dev/urandom. And maybe, don't put a 1 TB hard drive in a netbook or an older machine.
• eru 12y ago
  > Reservoir sampling is still O(N), and it requires generating a random number for every element. I agree with your comment in general. Only: you can do better than generate a random number for each element. (Generate a random number to tell you how many elements in the steam to skip.)
  • alok-g 12y ago
    Can you show that this will still maintain a uniform probability distribution?
    • eru 12y ago
      Yes.
    • shoegumfoot 12y ago
      > Can you show that [generating a number of records to skip instead of a yes/no for each record] will still maintain a uniform probability distribution? That should work if you pull the skip count from the appropriate distribution (negative binomial, I think).
      • eru 12y ago
        Yes, you have to work out the right distribution, and how to sample from it (at all, and perhaps how to sample from it efficiently).