Universal Perfect Samplers for Incremental Streams

) and the G-sampling problem is to select an index v * ∈ [n] according to its contribution to the Gmoment, i.e., such that P(v

Approximate G-samplers may introduce multiplicative and/or additive errors to this probability, and some have a non-trivial probability of failure.

In this paper we focus on the exact G-sampling problem, where G is selected from the following class of functions.

The class G is perhaps more natural than it looks. It captures all Laplace exponents of nonnegative, one-dimensional Lévy processes, and includes several well studied classes such as pth moments G(z) = z p , p ∈ [0, 1], logarithms G(z) = log(1 + z), Cohen and Geri's [6] soft concave sublinear functions, which are used to approximate concave sublinear functions, including cap statistics.

In this paper we develop G-samplers for a vector x ∈ R n + that is presented as an incremental stream of positive updates. In particular:

• For any G ∈ G, we give a very simple G-sampler that uses 2 words of memory and stores at all times a v * ∈

• We give a "universal" G-sampler that uses O(log n) words of memory w.h.p., and given any G ∈ G at query time, produces an exact G-sample.

With an overhead of a factor of k, both samplers can be used to G-sample a sequence of k indices with or without replacement.

Our sampling framework is simple and versatile, and can easily be generalized to sampling from more complex objects like graphs and hypergraphs.