3
$\begingroup$

This is a variant of my previous question (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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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" $\endgroup$
    – Suresh Venkat
    Jun 22, 2015 at 17:05
  • $\begingroup$ @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. $\endgroup$
    – Lior Kogan
    Jun 22, 2015 at 17:44
  • $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Jun 22, 2015 at 23:41
  • $\begingroup$ See math.stackexchange: Probability to choose specific item in a “weighted sampling without replacement” experiment - where the weights are known a priori. $\endgroup$
    – Lior Kogan
    Jun 23, 2015 at 5:04
  • $\begingroup$ See also Weighted Random Sampling over Data Streams definitions 2 and 3. $\endgroup$
    – Lior Kogan
    Jun 23, 2015 at 7:05

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Lior Kogan
    Jun 22, 2015 at 4:12
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jun 22, 2015 at 5:12
  • $\begingroup$ 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. $\endgroup$
    – Lior Kogan
    Jun 22, 2015 at 5:17
  • $\begingroup$ @LiorKogan, OK, got it. See edited answer for how you can address that. $\endgroup$
    – D.W.
    Jun 22, 2015 at 6:56
  • $\begingroup$ 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. $\endgroup$
    – Lior Kogan
    Jun 22, 2015 at 7:20
0
$\begingroup$

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 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, Moshe Ivry

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.