  Starting with a set of weighted items, we want to create a generic sample of
a certain size that we can later use to estimate the total weight of arbitrary
subsets. For this purpose, we propose priority sampling which tested on
Internet data performed better than previous methods by orders of magnitude.
  Priority sampling is simple to define and implement: we consider a steam of
items i=0,...,n-1 with weights w_i. For each item i, we generate a random
number r_i in (0,1) and create a priority q_i=w_i/r_i. The sample S consists of
the k highest priority items. Let t be the (k+1)th highest priority. Each
sampled item i in S gets a weight estimate W_i=max{w_i,t}, while non-sampled
items get weight estimate W_i=0.
  Magically, it turns out that the weight estimates are unbiased, that is,
E[W_i]=w_i, and by linearity of expectation, we get unbiased estimators over
any subset sum simply by adding the sampled weight estimates from the subset.
Also, we can estimate the variance of the estimates, and surpricingly, there is
no co-variance between different weight estimates W_i and W_j.
  We conjecture an extremely strong near-optimality; namely that for any weight
sequence, there exists no specialized scheme for sampling k items with unbiased
estimators that gets smaller total variance than priority sampling with k+1
items. Very recently Mario Szegedy has settled this conjecture.
