12 ms·
Reservoir Sampling
- pixelbeat 1y agoFWIW GNU coreutils' shuf uses reservoir sampling for larger inputs to give bounded memory operation
- wood_spirit 1y agoI remember this turning up in a google interview back in the day. The interview was really expecting me not to know the algorithm and to flounder about trying to solve the problem from first principles. Was fun to just shortcut things by knowing the answer that time.
- owyn 1y agoYeah, this was a google interview question for me too. I didn't know the algorithm and floundered around trying to solve the problem. I came up with the 1/n and k/n selection strategy but still didn't get the job lol. I think the guy who interviewed me was just killing time until lunch. I like the visualizations in this article, really good explanation.
- dekhn 1y agoI didn't know about the algorithm until after I got hired there. It's actually really useful in a number of contexts, but my favorite was using it to find optimal split points for sharding lexicographically sorted string keys for mapping. Often you will have a sorted table, but the underlying distribution of keys isn't known, so uniform sharding will often cause imbalances where some mappers end up doing far more work than others. I don't know if there is a convenient open source class to do this.
- wood_spirit 1y agoInteresting idea, hadn’t that about that way to apply it. I knew it from before my interview from a turbo pascal program I had seen that sampled dat tape backups of patient records from a hospital system. These samples were used for studies. That was a textbook example of it’s utility.
- dekhn 1y agoI guess the question in my mind is: would you expect a smart person who did not previously know this problem (or really much random sampling at all) to come up with the algorithm on the fly in an interview? And if the person had seen it before and memorized the answer, does that provide any signal of their ability to code?
- samwho 1y agoMy gut instinct is no. I certainly don't think I'd be able to derive this algorithm from first principles in a 60 minute whiteboarding interview, and I worked at Google for 4 years.
- wood_spirit 1y agoThey wanted to see your analytical thinking skills at work. To pass you only needed to be sensible. You didn’t fail the interview if you couldn’t invent reservoir sampling!
- dekhn 1y agouh, no, people would get a fail on the question if they didn't correctly identify both the initial selection and sample acceptance criteria.
- petters 1y agoThis also got me past one interview. I came up with k/n but now I think it's better to just generate a random float in [0, 1] and keep the k largest ones
- samwho 1y agoHello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)
- malwrar 1y agoLove your website’s design, I find all of interactivity, the dog character as an “audience”, and even the font/color/layout wonderful. Loved the article too!
- samwho 1y agoThank you so much! The dogs on the playing cards were commissioned just for this post. They’re all made by the wonderful https://www.andycarolan.com/ https://www.andycarolan.com/. The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ https://davidmathlogic.com/colorblind/. Oh, and you can pet the dogs. :)
- lol768 1y agoIt would've been easy to just use green for the held card and red for the discard pile. Thank you for using a colour-blind friendly palette; as someone with deuteranopia :)
- samwho 1y agoYou're welcome! I think it's a beautiful palette, and I think people have come to associate me with it now so I don't think I'll ever change. I view all of my posts using the various colour blindness filters in the Chrome dev tools during development, to make sure I'm not using any ambiguous pairings. I'm glad that effort made you feel welcome and able to enjoy the content fully.
- zerd 1y agoJust noticed the physics simulator at the top is interactive. Then I was stacking squares on top of each other to see how tall I could make it, and started throwing things at it angry birds style. Fun stuff.
- stygiansonic 1y agoGreat article and nice explanation. I believe this describes “Algorithm R” in this paper from Vitter, who was probably the first to describe it: https://www.cs.umd.edu/~samir/498/vitter.pdf https://www.cs.umd.edu/~samir/498/vitter.pdf
- fanf2 1y agoThat paper says “Algorithm R (which is a reservoir algorithm due to Alan Waterman)” but it doesn’t have a citation. Vitter’s previous paper https://dl.acm.org/doi/10.1145/358105.893 https://dl.acm.org/doi/10.1145/358105.893 cites Knuth TAOCP vol 2. Knuth doesn’t have a citation.
- stygiansonic 1y agoInteresting! If Knuth is not the original author then they’ve been lost to the sands of time
- svat 1y agoKnuth also says that "Algorithm R is due to Alan G. Waterman", on TAOCP vol 2 page 144, just below "Algorithm R (Reservoir sampling)". This blog post seems to be a good history of the algorithm: https://markkm.com/blog/reservoir-sampling/ https://markkm.com/blog/reservoir-sampling/ (it was given by Waterman in a letter to Knuth, as an improvement of Knuth's earlier "reservoir sampling" from the first edition). > All in all, Algorithm R was known to Knuth and Waterman by 1975, and to a wider audience by 1981, when the second edition of The Art of Computer Programming volume 2 was published.
- t55 1y agogreat article!
- phillipcarter 1y agoThis is a great post that also illustrates the tradeoffs inherent in telemetry collection (traces, logs, metrics) for analysis. It's a capital-H Hard space to operate in that a lot of developers either don't know about, or take for granted.
- samwho 1y agoSomething I've considered writing about in the past is how sampling affects the shape of lines on graphs. Render the same underlying data with different sampling strategies and show how the resulting graph can look extremely different depending on the strategy used. I think it's an underappreciated thing a lot of people don't think about when looking at their observability tools.
- phillipcarter 1y agoYeah it’s challenging. I work for such a tool and we re-weight counts which is generally the right move, but comes with its own subtleties like when you are looking for exact counts specifically to tune sampling, or your MoE is bad for the particular calculation and granularity of data. Observability: easily one of the more underestimated fields in computing.
- YZF 1y agoSampling theorem. It's interesting that people seem to think that sampling mathematics somehow applies to modems or RF but not to the data they are looking at. Things like aliasing absolutely matter for observability/telemetry.
- sadiq 1y agoThis is a really nicely written and illustrated post. An advanced extension to this is that there are algorithms which calculate the number of records to skip rather than doing a trial per record. This has a good write-up of them: https://richardstartin.github.io/posts/reservoir-sampling https://richardstartin.github.io/posts/reservoir-sampling
- magicalhippo 1y agoWe lived in a rural area when I was a kid. My dad told me once that his buddy had to measure the ptarmigan[1] population in the mountains each year as part of his job. He did this by hiking a fixed route, and at fixed intervals scare the birds so they would fly and count. The total count was submitted to some office which used it to estimate the population. One year he had to travel abroad when the counting had to be done, so he recruited a friend and explained in detail how to do it. However when the day of the counting arrived his friend forgot, and it was a huge hassle anyway so he just submitted a number he figured was about right, and that was that. Then one day the following year, the local newspaper had a frontpage headline stating "record increase in ptarmigan population". The reason it was big news was that the population estimate was used to set the hunting quotas, something his friend had not considered... [1]: https://en.wikipedia.org/wiki/Rock_ptarmigan https://en.wikipedia.org/wiki/Rock_ptarmigan
- codr7 1y agoNever trust statistics. I once worked on a reservation system for some pretty big ski resorts. We were running late, working nights, and one of the last things we had to finish was the official statistics reports about number of guest nights etc that gets published by the government. Lets just say that the statistics that year had little to do with reality.
- deleted 1y ago[deleted]
- amw-zero 1y agoYou’re confusing statistics with forecasting. We can and should trust statistics. We should just never trust their relation to future behavior.
- swiftcoder 1y agoFairly sure the previous poster is describing statistics that were made up, rather than measured/sampled. Those are, for hopefully obvious reasons, not very trustworthy
- foxbee 1y agoWonderful illustrations and writing. Real interesting read.
- hinkley 1y agoThis reminds me that I need to spend more time thinking about the algorithm the allies used to count German tanks by serial number. The people in the field estimated about 5x as many tanks as were actually produced but the serial number trick was over 90% accurate.
- dekhn 1y agohttps://en.wikipedia.org/wiki/German_tank_problem https://en.wikipedia.org/wiki/German_tank_problem
- hinkley 1y agoIt seems like it could have some utility in places where hyperloglog isn’t quite right. YouTube recommendations pointed me at a Numberphile video on this a couple weeks ago: https://youtube.com/watch?v=WLCwMRJBhuI https://youtube.com/watch?v=WLCwMRJBhuI
- skykooler 1y agoAn interesting corollary of this is that if you only have a single sample, it reduces to indicating that your sample is the median value - i.e. if you see one item with serial number N, you can guess that there were roughly 2N produced.
- hinkley 1y agoYou do have outliers though. Seal Team 6 is actually Seal Team 1 but they wanted people to think they were outnumbered.
- justanotheratom 1y agoGreat article and explanation. On a practical level though, this would be the last thing I would use for log collection. I understand that when there is a spike, something has to be dropped. What should this something be? I don't see the point of being "fair" about what is dropped. I would use fairness as a last resort, after trying other things: Drop lower priority logs: If your log messages have levels (debug, info, warning, error), prioritize higher-severity events, discarding the verbose/debug ones first. Contextual grouping: Treat a sequence of logs as parts of an activity. For a successful activity, maybe record only the start and end events (or key state changes) and leave out repetitive in-between logs. Aggregation and summarization: Instead of storing every log line during a spike, aggregate similar or redundant messages into a summarized entry. This not only reduces volume but also highlights trends.
- manmal 1y agoI’ve been down the observability rabbit hole recently, and what you’re describing is probably a mix of head and tail sampling: https://docs.honeycomb.io/manage-data-volume/sample/ https://docs.honeycomb.io/manage-data-volume/sample/
- justanotheratom 1y agohoneycomb seems quite mature, thanks.
- ted_dunning 1y agoThe article addressed this. In fact, you don't typically want to throw away all of the low priority logs ... you just want to limit them to a budget. And you want to limit the total number of log lines collected to a super budget. Reservoir sampling can handle all of that.
- HelloNurse 1y agoYou should drop or consolidate some entries if you can, but then the important entries that remain can still be too many and require random culling because anything is better than choking. Fair reservoir sampling can be made unfair in controlled ways (e.g. by increasing the probability of retaining an entry if its content is particularly interesting); it competes with less principled biased random (or less than random) selection algorithms as a technique of last resort.
- gregable 1y agoVery well put together. If you are curious about the weighted version, I tried to explain it some here: https://gregable.com/2007/10/reservoir-sampling.html https://gregable.com/2007/10/reservoir-sampling.html There's also a distributed version, easy with a map reduce. Or the very simple algorithm: generate a random paired for each item in the stream and keep the top N ordered by that random.
- tmoertel 1y agoTwo notes on the weighted version. First, the straightforward implementation of selecting the top N when ranked by POW(RANDOM(), 1.0 / weight) has stability problems when the weights are very large or very small. Second, the resulting sample does not have the same distribution in expectation as the population from which it was drawn. This is especially so when the overall weight is concentrated in a small number of population elements. But such samples are workable approximations in many cases. I discuss these issues more here: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
- lordnacho 1y agoI discovered this in one of those coding quizzes they give you to get a job. I was reviewing questions and one of them was this exact thing. I had no idea how to do it until I read the answer, and then it was obvious.
- tanvach 1y agoFrom data science perspective, the volume of the data also encodes really valuable information, so it’s good to also log the number of data points each one represents. For example, if sampling rate comes out to be 10%, have a field that encodes 10. This way you can rebuild and estimate most statistics like count, sum, average, etc.
- jbellis 1y agoUsed in Dropwizard Metrics, among other places. https://metrics.dropwizard.io/4.2.0/ https://metrics.dropwizard.io/4.2.0/
- hansvm 1y agoThis is a great post, very approachable, with excellent visualizations. We use a variation of this sort of thing at $WORK to solve a related problem, where you want to estimate some percentile from a running stream, with the constraints that the percentile you want to choose changes from time to time but is generally static for a trillion or more iterations (and the underlying data is quasi-stationary). If you back the process by a splay tree, you can get amortized O(1) percentile estimates (higher error bars for a given RAM consumption than a number of other techniques, but very fast). You can also play with the replacement probability to, e.g., have a "data half-life" (denominated either in time or discrete counts) and bias the estimate toward recent events, which is more suitable for some problems.
- Iwan-Zotow 1y agoInteresting
- vismit2000 1y agoThe famous 4 mins explanation of reservoir sampling: https://www.youtube.com/watch?v=A1iwzSew5QY https://www.youtube.com/watch?v=A1iwzSew5QY
- Lichtso 1y agoThe Weighted Reservoir Sampling (WRS) variant is used in ReSTIR (spatiotemporal reservoir resampling for real-time ray tracing). Which is a stochastic light transport estimator with inbuilt spatiotemporal denoising. A light transport estimator is trying to figure out how much light flows through a scene (https://en.wikipedia.org/wiki/Radiance https://en.wikipedia.org/wiki/Radiance). For that it has to integrate the radiance across all the possible paths light could take, while maintaining the conservation of energy (https://en.wikipedia.org/wiki/Rendering_equation https://en.wikipedia.org/wiki/Rendering_equation). In all but the most trivial cases this integral of the rendering equation has no tractable closed form solution and solving it is thus done stochastically. The very basic idea is the Monte Carlo method (https://en.wikipedia.org/wiki/Monte_Carlo_method https://en.wikipedia.org/wiki/Monte_Carlo_method): Randomly sample as many paths as you can and average them. From there more sophisticated sampling strategies were developed over the last decades: - Importance Sampling (IS) - Multiple Importance Sampling (MIS) - Sample Importance Resampling (SIR) - Resampled Importance Sampling (RIS) - Weighted Reservoir Sampling (WRS) - And finally combining RIS and WRS into ReSTIR For a in depth read see: https://agraphicsguynotes.com/posts/understanding_the_math_behind_restir_di/ https://agraphicsguynotes.com/posts/understanding_the_math_b...
- WhitneyLand 1y agoReminds me a bit of the Monte Hall problem, probability adjustment based on conditional information can lead to counterintuitive results.
- tuzemec 1y agoNice! This is almost in the same league with Bartosz Ciechanowski's articles - https://ciechanow.ski/ https://ciechanow.ski/
- samwho 1y agoBartosz is a huge inspiration to me, you can likely tell that there are plenty of things he does in his post that I'm emulating in mine. It's maybe the best compliment you can give me to compare my work to his. Thank you.
- Coeur 1y agoI love this kind of dynamic web interactive education. The other ones that come to mind are Bret Victor https://worrydream.com/ https://worrydream.com/ , Bartosz Ciechanowski https://ciechanow.ski/ https://ciechanow.ski/ , and Nicky Case has a nice page many more at https://explorabl.es/ https://explorabl.es/ .
- tomsonj 1y agovery cool - made me consider the contrasts with token-bucket rate limiting for log collection and stumbled across a interesting discussion https://github.com/open-telemetry/opentelemetry-specification/issues/1769#issuecomment-1061263696 https://github.com/open-telemetry/opentelemetry-specificatio...