Sampling distinct values with probability proportional to their frequency This is a variant of my previous question (Reservoir sampling of distinct values)

I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.

In my case, the stream contains many duplicate values, and I need to make sure that my sample set won't include any duplicate values. It is important to note the the number of distinct values in the stream is huge as well (to big to fit memory).

I need to make sure that the probability of any value being sampled is proportional (or about proportional) to its frequency in the stream.

Is there any way to achieve this?
If the problem is well-defined, I suspect it should be achievable using the following method.  Pick a $m$ values uniformly at random from the stream.  For each value, the expected value of the number of times it is included in the sample will be proportion to its frequency in the stream.  If the frequency of every item is small compared to $1/m$, the probability that an item appears in the sample will be approximately proportional to its frequency in the stream.

If some items appear more often than that, use a sketch (e.g., a CountMin sketch) to estimate the frequency of frequently-occurring items.  You don't need to estimate the frequency of all items, only those whose frequency is higher than $1/(1000m)$ (say), so the sketch can be very efficient.  Then, you select $m$ values uniformly at random from the stream, removing duplicates; if any of the selected values is in the CountMin sketch and has probability close to $1/m$ or larger, then you fix things up (e.g., by dropping it with some probability, as needed).  I'll let you work out the exact arithmetic for how to make the probabilities work out however you want (as it's not clear to me exactly what you want to have happen), but this should work and be very efficient, as the sketch only needs to track frequencies for a small number of items.