Adaptive Threshold Sampling
  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.
