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

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

CC BY-SA 3.0
2015-06-22T04:12:27.983Z
Thanks, but there are two problems: the sample set may include duplicates, and the length of the stream is unknown so it can't be sampled uniformly.
Lior Kogan
CC BY-SA 3.0
2015-06-22T05:12:49.703Z
@LiorKogan, if the frequency of every item is small compared to $1/m$, then with high probability the sample set won't include duplicates (if you use my proposed method).  You *can* sample uniformly from a stream even without knowing its length, using reservoir sampling -- that's exactly what the standard textbook reservoir sampling scheme gives you.
D.W.
CC BY-SA 3.0
2015-06-22T05:17:10.853Z
In my case some values may be 1000's of times more frequent than others. In extreme cases a single value may appear in more than half of the stream.
Lior Kogan
CC BY-SA 3.0
2015-06-22T06:56:40.270Z
@LiorKogan, OK, got it.  See edited answer for how you can address that.
D.W.
CC BY-SA 3.0
2015-06-22T07:20:03.513Z
Wouldn't this method require two passes over the stream? One for constructing the sketch and one for sampling? I can use only one pass. In addition, note that I don't know anything a priori regarding the amount of different values, their frequencies or their distribution along the stream.
Lior Kogan
CC BY-SA 3.0
2015-06-22T16:48:37.687Z
@LiorKogan, no, you can do both of them in parallel: as each new item arrives, you feed it both to the reservoir sampling and to the sketch.  There's no need for two passes over the stream.  Also, my answer doesn't require any a priori knowledge of any of those factors.  Perhaps spend a little time studying reservoir sampling and sketches to become familiar with them?
D.W.
CC BY-SA 3.0
2015-06-22T16:54:27.560Z
Trust me I know both well ;-) proving (or disproving) the probability properties for your suggest method is far from trivial ;-)
Lior Kogan
CC BY-SA 3.0
2015-06-22T00:50:06.937Z
2015-06-24T01:09:24.147Z
2015-06-24T01:09:24.147Z
D.W.
<p>I had the same problem and after thinking about it a while, i think the solution could be a simple variation on <a href="https://en.wikipedia.org/wiki/Reservoir_sampling#Reservoir_with_Random_Sort" rel="nofollow noreferrer">Reservoir with Random Sort</a> algorithm. The variation takes into account the existence of duplicates. If a coming stream element <code>S.Current</code> is already contained in the priority queue <code>H</code>, and a new  associated random value <code>r</code> of it is lower than the one that is stored, than <code>H</code> is updated with that new random value for <code>S.current</code>. This way you keep a 'fair' chance for each element in the stream and take control of the duplicates.</p>

<p>Cheers,
Moshe Ivry</p>

CC BY-SA 4.0
2018-06-14T14:29:38.413Z
2018-06-14T14:29:38.413Z
Moshe Ivry
<p>This is a variant of my previous question (<a href="https://cstheory.stackexchange.com/questions/31789/reservoir-sampling-of-distinct-values">Reservoir sampling of distinct values</a>)</p>

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

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

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

CC BY-SA 3.0
2015-06-22T17:05:19.897Z
Suppose your stream had one element occurring 1000 times, and another that occurred 10 times and everything else occurred one time. Suppose you wanted 4 samples. What would be an acceptable outcome here  ? Basically I don't understand how you can expect both "probability proportional to frequency" and "no duplicates"
Suresh Venkat
CC BY-SA 3.0
2015-06-22T17:44:05.257Z
@SureshVenkat: The probability that the element that occurs 1000 times would be in the sample set should be 1000 times higher than the probability of any of the elements that occur once would be in the sample set.
Lior Kogan
CC BY-SA 3.0
2015-06-22T23:41:30.773Z
My point is that since you require no duplicates in the sample returned, there's no way to guarantee what you're asking. For example, imagine running your sampling algorithm a number of times to get many different 4-element samples. In each of these, the very frequent element will likely occur, but so will the other items, and in fact they'll have to occur fairly often by the pigeonhole principle. Am I just confused ?
Suresh Venkat
CC BY-SA 3.0
2015-06-23T05:04:22.877Z
See math.stackexchange: [Probability to choose specific item in a “weighted sampling without replacement” experiment](http://math.stackexchange.com/questions/316175/probability-to-choose-specific-item-in-a-weighted-sampling-without-replacement) - where the weights are known a priori.
Lior Kogan
CC BY-SA 3.0
2015-06-23T07:05:51.277Z
See also [Weighted Random Sampling over Data Streams](http://arxiv.org/pdf/1012.0256.pdf) definitions 2 and 3.
Lior Kogan
<ds.algorithms><pr.probability><streaming-algorithms>
Sampling distinct values with probability proportional to their frequency
Lior Kogan
# Sampling distinct values with probability proportional to their frequency

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

This is a variant of my previous question ([Reservoir sampling of distinct values](https://cstheory.stackexchange.com/questions/31789/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?

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

> **Comments:**
> **username_1**: Suppose your stream had one element occurring 1000 times, and another that occurred 10 times and everything else occurred one time. Suppose you wanted 4 samples. What would be an acceptable outcome here  ? Basically I don't understand how you can expect both "probability proportional to frequency" and "no duplicates"  
> **username_0**: @SureshVenkat: The probability that the element that occurs 1000 times would be in the sample set should be 1000 times higher than the probability of any of the elements that occur once would be in the sample set.  
> **username_1**: My point is that since you require no duplicates in the sample returned, there's no way to guarantee what you're asking. For example, imagine running your sampling algorithm a number of times to get many different 4-element samples. In each of these, the very frequent element will likely occur, but so will the other items, and in fact they'll have to occur fairly often by the pigeonhole principle. Am I just confused ?  
> **username_0**: See math.stackexchange: [Probability to choose specific item in a “weighted sampling without replacement” experiment](http://math.stackexchange.com/questions/316175/probability-to-choose-specific-item-in-a-weighted-sampling-without-replacement) - where the weights are known a priori.  
> **username_0**: See also [Weighted Random Sampling over Data Streams](http://arxiv.org/pdf/1012.0256.pdf) definitions 2 and 3.  

---

## 2 answers

### Answer by username_2 on 2015-06-22. Score: 2

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.

> **Comments:**
> **username_0**: Thanks, but there are two problems: the sample set may include duplicates, and the length of the stream is unknown so it can't be sampled uniformly.  
> **username_2**: @LiorKogan, if the frequency of every item is small compared to $1/m$, then with high probability the sample set won't include duplicates (if you use my proposed method).  You *can* sample uniformly from a stream even without knowing its length, using reservoir sampling -- that's exactly what the standard textbook reservoir sampling scheme gives you.  
> **username_0**: In my case some values may be 1000's of times more frequent than others. In extreme cases a single value may appear in more than half of the stream.  
> **username_2**: @LiorKogan, OK, got it.  See edited answer for how you can address that.  
> **username_0**: Wouldn't this method require two passes over the stream? One for constructing the sketch and one for sampling? I can use only one pass. In addition, note that I don't know anything a priori regarding the amount of different values, their frequencies or their distribution along the stream.  
> **username_2**: @LiorKogan, no, you can do both of them in parallel: as each new item arrives, you feed it both to the reservoir sampling and to the sketch.  There's no need for two passes over the stream.  Also, my answer doesn't require any a priori knowledge of any of those factors.  Perhaps spend a little time studying reservoir sampling and sketches to become familiar with them?  
> **username_0**: Trust me I know both well ;-) proving (or disproving) the probability properties for your suggest method is far from trivial ;-)  

---

### Answer by username_3 on 2018-06-14. Score: 0

I had the same problem and after thinking about it a while, i think the solution could be a simple variation on [Reservoir with Random Sort](https://en.wikipedia.org/wiki/Reservoir_sampling#Reservoir_with_Random_Sort) algorithm. The variation takes into account the existence of duplicates. If a coming stream element `S.Current` is already contained in the priority queue `H`, and a new associated random value `r` of it is lower than the one that is stored, than `H` is updated with that new random value for `S.current`. This way you keep a 'fair' chance for each element in the stream and take control of the duplicates.

Cheers,
username_3


---

