  From a high volume stream of weighted items, we want to maintain a generic
sample of a certain limited size $k$ that we can later use to estimate the
total weight of arbitrary subsets. This is the classic context of on-line
reservoir sampling, thinking of the generic sample as a reservoir. We present
an efficient reservoir sampling scheme, $\varoptk$, that dominates all previous
schemes in terms of estimation quality.
  $\varoptk$ provides {\em variance optimal unbiased estimation of subset
sums}. More precisely, if we have seen $n$ items of the stream, then for {\em
any} subset size $m$, our scheme based on $k$ samples minimizes the average
variance over all subsets of size $m$. In fact, the optimality is against any
off-line scheme with $k$ samples tailored for the concrete set of items seen.
In addition to optimal average variance, our scheme provides tighter worst-case
bounds on the variance of {\em particular} subsets than previously possible. It
is efficient, handling each new item of the stream in $O(\log k)$ time.
Finally, it is particularly well suited for combination of samples from
different streams in a distributed setting.
