# 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

## 1 Answer

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.

• Thanks! The only problem is that this is sampling with replacement as one element may have the minimal value in more than one hash function. Therefore we may end up with less than n distinct samples! – Lior Kogan Jun 18 '15 at 6:58
• I used your method with some modifications: (1) When a MinHash is updated i break the hash-functions loop. This ensure sampling without replacement, but some hash functions may be left unused. (2) Using twice as many hash functions than need. (3) Trimming unused hash functions. – Lior Kogan Jun 18 '15 at 7:22
• I wouldn't call it it my method =). In any case, using the bottom-k (as opposed to just the smallest) should work as well (with some extra work). This way there is no repetition. – Tsvi Kopelowitz Jun 18 '15 at 14:29
• bottom-k is indeed the correct way for sampling distinct values without replacement. Thanks again. – Lior Kogan Jun 20 '15 at 18:03