Adaptive Threshold Sampling
This work addresses the challenge of adaptive sampling in streaming data for researchers and practitioners in computer science and statistics, offering a general solution that simplifies estimator design.
The authors tackled the problem of adaptive sampling in data streams, where pre-selecting sampling probabilities is often infeasible, by developing a framework that allows adaptive threshold adjustments while maintaining independence-like properties for unbiased estimators. They applied this framework to design new samplers for various problems, including a top-K sampling procedure with adaptive sketch sizes and probabilities.
Sampling is a fundamental problem in computer science and statistics. However, for a given task and stream, it is often not possible to choose good sampling probabilities in advance. We derive a general framework for adaptively changing the sampling probabilities via a collection of thresholds.In general, adaptive sampling procedures introduce dependence amongst the sampled points, making it difficult to compute expectations and ensure estimators are unbiased or consistent. Our framework address this issue and further shows when adaptive thresholds can be treated as if they were fixed thresholds which samples items independently. This makes our adaptive sampling schemes simple to apply as there is no need to create custom estimators for the sampling method. Using our framework, we derive new samplers that can address a broad range of new and existing problems including sampling with memory rather than sample size budgets, stratified samples, multiple objectives, distinct counting, and sliding windows. In particular, we design a sampling procedure for the top-K problem where, unlike in the heavy-hitter problem, the sketch size and sampling probabilities are adaptively chosen.