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

• Papers on $\ell_0$ sampling, namely sampling distinct elements are what you may be looking for. Here is one paper: arxiv.org/abs/1012.4889 – Chandra Chekuri Jun 18 '15 at 4:39

This is something that min-wise independent hashing is good for. (See a wikipedia explanation here. The idea is to use a family $\mathcal{H}$ of hash functions so that when you pick a random function $h\in H$ from the family, for any set $S$ of $n$ elements, for any $x\notin S$, $\Pr_{h\in \mathcal{H}}[h(x) < \min_{y\in S} \{h(y)\}] = \frac{1}{n+1}$. This means that every element in $S$ has the same likelihood of being the only one with the smallest hashed value.
As you scan the stream, keep track of the smallest hashed value that you have seen, and whichever element was mapped to that value is your sample. There are families of hash functions that are almost minwise independent families. For example a paper by Dahlgaard and Thorup . If you want to sample $k$ elements you could do this naively using $k$ hash functions, but you could also use ideas from bottom-$k$ sketching with only one function. See this paper by Thorup.