  Random samples are lossy summaries which allow queries posed over the data to
be approximated by applying an appropriate estimator to the sample. The
effectiveness of sampling, however, hinges on estimator selection. The choice
of estimators is subjected to global requirements, such as unbiasedness and
range restrictions on the estimate value, and ideally, we seek estimators that
are both efficient to derive and apply and {\em admissible} (not dominated, in
terms of variance, by other estimators). Nevertheless, for a given data domain,
sampling scheme, and query, there are many admissible estimators. We study the
choice of admissible nonnegative and unbiased estimators for monotone sampling
schemes. Monotone sampling schemes are implicit in many applications of massive
data set analysis. Our main contribution is general derivations of admissible
estimators with desirable properties. We present a construction of {\em
order-optimal} estimators, which minimize variance according to {\em any}
specified priorities over the data domain. Order-optimality allows us to
customize the derivation to common patterns that we can learn or observe in the
data. When we prioritize lower values (e.g., more similar data sets when
estimating difference), we obtain the L$^*$ estimator, which is the unique
monotone admissible estimator. We show that the L$^*$ estimator is
4-competitive and dominates the classic Horvitz-Thompson estimator. These
properties make the L$^*$ estimator a natural default choice. We also present
the U$^*$ estimator, which prioritizes large values (e.g., less similar data
sets). Our estimator constructions are both easy to apply and possess desirable
properties, allowing us to make the most from our summarized data.
