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