4
$\begingroup$

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem.

On a stream of length $n$, I would like to make $o(n)$ calls to my random number generator (henceforth "RNG"). Additionally, I would like to work in finite precision. Is there a data structure that supports this?

As usual with reservoir sampling, I want to preserve that:

  • Each item is selected with equal probability
  • The total time used is $O(n)$ with high probability. A Las Vegas algorithm would be just fine
  • No more than $O(1)$ machine words and $O(1)$ stream items are stored between stream items arriving
  • Only one pass is made over the stream

Results that I know about that do not meet my requirements include:

  • The standard reservoir sampling data structure makes $\Omega(n)$ calls to the RNG.

  • "Random sampling with a reservoir" by Jeffrey S. Vitter and "Reservoir-sampling algorithms of time complexity $O(n(1 + \log(N/n)))$" by Kim-Hung Li need only $o(n)$ calls to the RNG but use arbitrary precision arithmetic.

  • "Sampling in Space Restricted Settings" by Bhattacharya et al. describes a data structure that meets the above criteria but can fail to sample an item with non-zero probability.

  • Exact minwise hashing (in which each index in the stream is hashed and the reservoir holds the item at the index with the lowest hash value seen so far) would suffice, but exact minwise hashing families have size at least $e^{n - o(n)}$ according to Theorem 1 of "Min-Wise Independent Permutations" by Broder et al.. Storing a member of the family would require using at least $(\lg e)(n - o(n))$ bits of space between the arrival of stream items.

$\endgroup$
  • 1
    $\begingroup$ What if each time you draw a variable (approximately) that represents the number of items to be ignored until the next sample? Since reservoir sampling samples item $i$ with probability of $1/i$ this would mean $O(\log n)$ RNG access. $\endgroup$ – R B May 28 '17 at 8:52
  • $\begingroup$ @RB, that is a great idea, and it is how the Vitter and Li papers operate. However, they use arbitrary precision arithmetic to draw that variable. $\endgroup$ – jbapple May 28 '17 at 16:08
3
$\begingroup$

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number.

Building block: sampling without arbitrary precision arithmetic

Suppose we want to sample a discrete random variable $X$ from a distribution with cdf $F$ (i.e., $F(x) = \Pr[X \le x]$). Then one approach is to sample $y$ uniformly at random from $[0,1]$, find $x$ such that $F(x-1) < y \le F(x)$, and output $x$. This requires arbitrary precision arithmetic.

Here is a variant that avoids the need for arbitrary precision arithmetic, at the cost of making the algorithm a Las Vegas algorithm (so the worst-case running time is unbounded but the expected running time is nicely bounded). Basically, we sample the bits of $y$ one at a time, and stop as soon as we know what answer the prior method would output. At the $b$th stage, we know the first $b$ bits of $y$, i.e., we know $\tilde{y}$ such that $y \in [y, y + 1/2^b)$ and $2^b \tilde{y}$ is an integer. Now, we find $x$ such that $F(x-1) < \tilde{y} \le F(x)$. If $F(x-1) < \tilde{y}$ and $\tilde{y} + 1/2^b \le F(x)$, then we output $x$ and stop. (In this case, we don't know what the exactly value of $y$ is, but we still know it satisfies $F(x-1)< y \le F(x)$, so $x$ is certainly the right answer.) Otherwise, we output nothing and continue, sampling the next bit of $y$.

What's the running time of this procedure? The expected time until termination is $O(\lg n)$, where $n$ is the number of different possible values of $X$. (Why? Because at the $b$th stage, at most $n$ out of the $2^b$ possible values for $\tilde{y}$ will cause us to continue on to the $b+1$th stage. In particular, once $b$ exceeds $\lg n$, each stage has at least a one-half probability of terminating.) So, this gives a Las Vegas algorithm to sample from $X$, with exactly the right distribution, and with $O(\lg n)$ expected bits sampled from the RNG.

Solving your problem

Now we can solve your particular problem. We simply apply Vitter's algorithm (e.g., Algorithm Y), but instead of sampling the random value $\mathscr{S}$ using arbitrary-precision arithmetic, instead use the method described above.

How many random bits do we need? Based on the results in that paper, the expected number of times we need to sample $\mathscr{S}$ is $O(\log n)$, where $n$ is the length of the stream. Also each time we sample $\mathscr{S}$ the expected number of bits we need to sample is $O(\log n)$. Therefore, we'll need $O((\log n)^2)$ bits from the RNG, on average.

Also the total (expected) running time will be $O(n)$, if you use Vitter's efficient algorithms for sampling $\mathscr{S}$ (e.g., Algorithm Y and binary search or Newton's method).

$\endgroup$
  • $\begingroup$ For the method that Vitter gives to calculate the cdf $F$, it is not clear to me that the procedure "Now, we find $x$ such that $F(x-1) < \tilde{y} \le F(x)$." is possible in finite-precision arithmetic. Can you elaborate on how that would work with the $F$ in question? $\endgroup$ – jbapple May 29 '17 at 5:43
  • $\begingroup$ @jbapple, good point. I didn't check that, for the specific $F$ in the Vitter paper. It appears $F$ has the form $F(x) = (x+1)/(t+x+1)$, where $t$ is the number of records processed so far. I guess the question is whether we can compute the first $b$ bits of $(x+1)/(t+x+1)$ for all integers $x,t$ in the range $\{0,1,\dots,n\}$ (how far out do we have to go, to be sure of the $b$th bit?). So there's a gap here that I haven't thought through -- perhaps you can work through whether this works or whether that's a fatal flaw? $\endgroup$ – D.W. May 29 '17 at 6:01
  • $\begingroup$ Good point - I had missed that $F$ is much simpler in the case where the size of the reservoir, which Vitter calls $n$, is 1. I think it should be possible to get the quotient bit-by-bit by using long division on single (or at most double) precision numbers. That would do some of the work of arbitrary-precision numbers without requiring more general support for the functions that Vitter and Li use with arbitrary precision, like $\exp$ and $\log$. $\endgroup$ – jbapple May 29 '17 at 17:30

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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