Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reservoir Sampling

samwho.dev

Post reply on HN
Print view View original

71–80 of 107 posts

Re: Reservoir Sampling

#71

Post by YZF »

samwho wrote: post #36
phillipcarter wrote: post #6

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

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

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

Re: Reservoir Sampling

#72

Post by wood_spirit »

dekhn wrote: post #22
wood_spirit wrote: post #18

Earlier quoted context omitted.

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

I 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?

They 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!

Re: Reservoir Sampling

#73

Post by [deleted] »

codr7 wrote: post #58
magicalhippo wrote: post #9

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

Never 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]

Re: Reservoir Sampling

#74

Post by purrcat259 »

samwho wrote: post #3

Hello! 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 and is MIT licensed, so you’re welcome to use it :)

I just listened to your episode on fafo.fm a few days ago and recognised your handle and already knew the link was worth clicking. Your stuff is awesome!

Re: Reservoir Sampling

#75

Post by DonHopkins »

samwho wrote: post #11
malwrar wrote: post #10

Earlier quoted context omitted.

Love 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!

Thank 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/ . The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ . Oh, and you can pet the dogs. :)

So many nice touches that combine to be much more than the sum of the parts.

Doe's bandana is cool, your dogs must worship you for your commitment to them!

My only suggestion is a way to slow down or ^S the log to read the funny messages, since they were flying by so fast I could only get a glimpse, even with reservoir sampling.

something something "needs more emojis"! ;)

Re: Reservoir Sampling

#77

Post by dan-robertson »

eru wrote: post #48
samwho wrote: post #3

Hello! 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 and is MIT licensed, so you’re welcome to use it :)

Very nice post! Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement. That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on…

Alias tables are neat and not super well known. We used to have an interview question around sampling from a weighted distribution (typical answer: prefix sum -> binary search) and I don’t think anyone produced this. I like the explanation in that blog. The way it was explained to me was first ‘imagine drawing a bar chart and throwing a dart at it, retrying if you miss. This simulates the distribution but runs in expected linear time’. Then you can describe how to chop up the bars to fit in the rectangle you would get if all weights were equal. Proof that the greedy algorithm works is reasonably straightforward.

Re: Reservoir Sampling

#78

Post by Lichtso »

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

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

Re: Reservoir Sampling

#79

Post by slig »

samwho wrote: post #3

Hello! 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 and is MIT licensed, so you’re welcome to use it :)

It's so nice to read things written by someone who cares. Thank you so much for sharing!

Re: Reservoir Sampling

#80

Post by eru »

dan-robertson wrote: post #77
eru wrote: post #48

Earlier quoted context omitted.

Very nice post! Another interesting direction you can take reservoir sampling is instead of drawing a random number for each item (to see whether it replaces an existing item and which one), you generate a number from a geometric distribution telling you how many items you can safely skip before the next replacement. That's especially interesting, if you can skip many items cheaply. Eg because you can fast forward on…

Alias tables are neat and not super well known. We used to have an interview question around sampling from a weighted distribution (typical answer: prefix sum -> binary search) and I don’t think anyone produced this. I like the explanation in that blog. The way it was explained to me was first ‘imagine drawing a bar chart and throwing a dart at it, retrying if you miss. This simulates the distribution but runs in exp…

I'm not actually sure this makes for a good interview question. Doesn't it mostly just test whether you've heard of the alias method?

Btw, a slightly related question:

Supposed you have a really long text file, how would you randomly sample a line? Such that all lines in the text file have the exactly same probability. Ideally, you want to do this without spending O(size of file) time preprocessing.

(I don't think this is a good interview question, but it is an interesting question.)

One way: sample random characters until you randomly hit a newline. That's the newline at the end of your line.

Post reply on HN