<p>This is something that min-wise independent hashing is good for. (See <a href="https://en.wikipedia.org/wiki/MinHash" rel="nofollow">a wikipedia explanation here</a>. 
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) &lt; \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.</p>

<p>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 <em>almost</em> minwise independent families. For example <a href="http://arxiv.org/abs/1404.6724" rel="nofollow">a paper by Dahlgaard and Thorup  </a>.
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 <a href="http://arxiv.org/abs/1303.5479" rel="nofollow">this paper by Thorup</a>. </p>

CC BY-SA 3.0
2015-06-18T06:58:00.723Z
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
CC BY-SA 3.0
2015-06-18T07:22:54.240Z
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
CC BY-SA 3.0
2015-06-18T14:29:51.770Z
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
CC BY-SA 3.0
2015-06-20T18:03:28.173Z
bottom-k is indeed the correct way for sampling distinct values without replacement. Thanks again.
Lior Kogan
CC BY-SA 3.0
2015-06-17T22:34:52.147Z
2015-06-21T19:50:47.203Z
2015-06-21T19:50:47.203Z
Tsvi Kopelowitz
<p>I'm faced with a situation where I need to get <em>m</em> samples from a data stream (without replacement). Only one pass through the data is possible.</p>

<p>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).</p>

<p>Standard reservoir sampling algorithms (e.g. Algorithm R) ensure that the probability of any <strong>index</strong> being sampled is equal or about equal. In my case however, I need to make sure that the probability of any <strong>value</strong> being sampled is equal, or about equal.</p>

<p>Is there any way to achieve this?</p>

CC BY-SA 3.0
2015-06-18T04:39:22.440Z
Papers on $\ell_0$ sampling, namely sampling distinct elements are what you may be looking for. Here is one paper: http://arxiv.org/abs/1012.4889
Chandra Chekuri
<ds.algorithms><pr.probability><streaming-algorithms>
Reservoir sampling of distinct values
Lior Kogan
# Reservoir sampling of distinct values

(Asked by: username_0 on 2015-06-17)

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?

**Tags:** ds.algorithms, pr.probability, streaming-algorithms

> **Comments:**
> **username_1**: Papers on $\ell_0$ sampling, namely sampling distinct elements are what you may be looking for. Here is one paper: http://arxiv.org/abs/1012.4889  

---

## 1 answers

### Answer by username_2 on 2015-06-17. Score: 5 | Accepted answer

This is something that min-wise independent hashing is good for. (See [a wikipedia explanation here](https://en.wikipedia.org/wiki/MinHash).
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](http://arxiv.org/abs/1404.6724) .
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](http://arxiv.org/abs/1303.5479).

> **Comments:**
> **username_0**: 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!  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: bottom-k is indeed the correct way for sampling distinct values without replacement. Thanks again.  

---

