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 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).
Standard reservoir sampling algorithms (e.g. Algorithm R) ensure that the probability of any index being sampled is equal or about equal. In my case however, I need to make sure that the probability of any value being sampled is equal, or about equal.
Is there any way to achieve this?