Estimation for monotone sampling

DOI10.1145/2611462.2611485MaRDI QIDQ2943617zbMATH OpenOpenAlexFDO

Authors Edith Cohen

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1212.0243

zbMATH Keywords

monotone sampling\(L^*\) estimatorcoordinated samplingorder-optimal estimatorsvariance competitiveness

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Information storage and retrieval of data (68P20)

Abstract: 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${}^{\ast }$ estimator, which is the unique monotone admissible estimator. We show that the L${}^{\ast }$ estimator is 4-competitive and dominates the classic Horvitz-Thompson estimator. These properties make the L${}^{\ast }$ estimator a natural default choice. We also present the U${}^{\ast }$ 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.

Recommendations

• Estimation of a monotone density in \(s\)-sample biased sampling models
• On the estimation of monotone uniform approximations
• Sample selection models with monotone control functions
• On the sample monotonization problem
• Estimation of a discrete monotone distribution
• Estimation Under Purposive Sampling
• Efficient estimation of monotone boundaries
• Stochastic comparisons of stratified sampling techniques for some Monte Carlo estimators

Cited in

(3)

• Surprise sampling: improving and extending the local case-control sampling
• What you can do with coordinated samples
• Real-valued embeddings and sketches for fast distance and similarity estimation

This page was built for publication: Estimation for monotone sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943617)