Adaptive Threshold Sampling-Daniel Ting (Tableau Software).pdf

Bigbig

119

14页

0次

2022-07-20

免费下载

Adaptive threshold sampling

Daniel Ting

∗

Tableau Research

Seattle, Washington

dting.tr@gmail.com

ABSTRACT

Sampling is a fundamental problem in computer science and statis-

tics. 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 di-

cult 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 xed thresh-

olds 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, stratied samples,

multiple objectives, distinct counting, and sliding windows. In par-

ticular, we design a sampling procedure for the top-K problem

where, unlike in the heavy-hitter problem, the sketch size and sam-

pling probabilities are adaptively chosen.

CCS CONCEPTS

• Mathematics of computing → Probabilistic algorithms

;

•

Theory of computation → Sketching and sampling;

KEYWORDS

Streaming, priority sampling, Top-k, heavy hitters, distinct count-

ing, sliding windows, data sketching

ACM Reference Format:

Daniel Ting. 2022. Adaptive threshold sampling. In Proceedings of the 2022

International Conference on Management of Data (SIGMOD ’22), June 12–17,

2022, Philadelphia, PA, USA. ACM, New York, NY, USA, 14 pages. https:

//doi.org/10.1145/3514221.3526122

1 INTRODUCTION

Sampling is a fundamental problem in computer science and statis-

tics. By reducing the amount of data processed, it can signicantly

improve performance and lower costs, or it can ensure that the data

∗

This work was done while the author was employed at Tableau Software.

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than the

author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or

republish, to post on servers or to redistribute to lists, requires prior specic permission

and/or a fe e. Request permissions from permissions@acm.org.

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

ACM ISBN 978-1-4503-9249-5/22/06.

https://doi.org/10.1145/3514221.3526122

processed ts within a system’s resource constraints. Of particular

interest are random sampling without replacement procedures as

they do not sample redundant information.

Before observing the data, it is not possible to choose appropriate

sampling probabilities. For example, given a weighted stream of

unknown length, it is impossible to choose a sampling probability

ahead of time that ensures the sample satises a nite memory

budget

⌫

. To guarantee a nite budget is satised, each item’s

inclusion decreases the available budget and aects the inclusion

probability of other items.

This dependence causes several diculties when designing sam-

pling procedures and deriving estimators. In particular, the depen-

dence often makes it intractable to compute the inclusion probabil-

ity for each item or sets of items. When these sampling probabilities

cannot be estimated, the sample is almost useless in data analysis.

Good estimates cannot be obtained since estimators must adjust

the contribution of each item based on its inclusion probability.

These diculties can extend to designing sampling procedures.

When the sample size is not xed, items can be drawn indepen-

dently with weight

with probability

/ F

. For example, the

Conditional Poisson Sampling scheme is one that draws a xed size

sample and has desirable properties; however, no known algorithm

can eciently draw Conditional Poisson samples.

We propose a framework, adaptive threshold sampling, that ad-

dresses all of these challenges. We use it to solve novel problems

and improve existing solutions. In this framework, samples are easy

to draw; sample sizes and probabilities can change on the y; and

good estimators can be derived even though samples are dependent.

This framework mimics drawing independent (Poisson) samples.

Each item

is associated with an independent random value

and

a threshold

)

. The item is included in the sample if

< )

. Rather

than choosing a constant threshold

)

, we adjust the threshold in a

data and sample dependent way to obtain desirable properties.

Our methodological contributions revolve around making it sim-

ple to build thresholds where the resulting sample is easy to analyze.

We establish conditions when the threshold

)

can be treated as

if it was a xed threshold that yields an independent sample. This

simplies analysis of the sample since one can apply an existing un-

biased estimator for independent samples. Deriving and analyzing a

custom estimator based on the true sampling distribution becomes

unnecessary. When the conditions do not hold, we introduce a

more general notion of threshold recalibration that makes it easy

to compute expectations and derive new unbiased estimators for a

broader class of thresholding rules. We also provide methods for

building and composing thresholds and for merging samples. We

also prove an empirical process convergence result that further sim-

plies the development of goo d estimators and sampling designs.

It extends our theory for unbiased estimators and shows when

consistent estimators for independent samples remain consistent

Session 22: Provenance and Uncertainty

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1612

when applied to adaptive thresholding samples. It also provides

justication for heuristic thresholding schemes that do not satisfy

our conditions for unbiased estimation but satisfy an asymptotic

convergence condition which may be easier to verify.

Our contributions to applications exploits our methodological

contributions to develop new or improved sketches and estima-

tors on a range of new and existing problems. For example, we

double the eectiveness of the state-of-the-art in sampling from

sliding windows [

] even though we use exactly the same sketch

to construct the sample. We improve merge procedures for distinct

counting sketches, handle budget constraints for samples given

variable length items, and provide a solution to a novel top-k prob-

lem, a more challenging variation of the well-studied heavy hitter

problem, where the top-k items by frequency must be returned

regardless of how small their frequency may be.

1.1 Related work

A long line of work has studied the bottom-k sample [

showing how it can be used to draw weighted samples while de-

riving good estimators for sums over subpopulations as well as

estimates of their variance. These bottom-k sampling methods can

be considered an adaptive threshold sampling method where the

threshold ensures the sample size is exactly

. Extensions [

]

study combining bottom-k samples. Another techniques for e-

ciently drawing xed size : samples is VarOpt sampling [7].

Little work has provided generalizations of the bottom-k thresh-

olding rule while providing a unbiased estimators. One notable

exception is in distinct counting applications using

Uniform(

)

priorities. The Theta sketch [

] provides a general 1-goodness

condition. Thresholding rules that satisfy this ensure cardinality

estimates are unbiased. For uniform sampling, a generalized thresh-

olding rule has been used for distributed sampling [33].

In addition to providing an adaptive sampling framework, our

contributions also use it to address novel problems and improve

existing methods. Novel problems include sampling with xed mem-

ory budgets, multi-stratie d sampling, and top-k queries. These

problems are more dicult variations of existing problems. Exam-

ples of existing sketches and sampling methods that are improved

include sampling in sliding windows [

] and distinct counting

[

]. Our applications are provided as examples of our frame-

work’s usefulness. Bottom-k methods have been used in numerous

other applications such as set similarity [

], networking [

], time-

decayed sampling [10], and distributed sampling [13, 19, 33]

2 SAMPLING DESIGN AND ESTIMATION

We rst review sampling without replacement and the use of xed

thresholds for drawing samples. One key contribution of our pa-

per is under what conditions can a random, adaptive threshold be

treated as if it was a xed threshold.

The notion of weighted or unequal probability sampling is at

the core of many sampling problems. Sampling more informative

items with higher probability leads to lower variance estimates.

Choosing an appropriate measure of informativeness allows for

accurate estimation for problems ranging from simple aggregates

to complex machine learning models [

]. Unequal probability

sampling can also arise in other situations, such as in stratied

sampling where strata can have dierent sampling probabilities

or in distributed sampling where nodes may make independent

choices about the sampling rate.

2.1 Poisson sampling with thresholds

The simple sampling scheme where the inclusion decisions for each

item is independent of all others is of particular interest. That is

⇠ ⌫4A=>D;;8( c

) (1)

where

1 if item

is included in the sample. Such schemes

are called Poisson Sampling designs. This is not to be confused

with Poisson distributed random variables. In this case, the desired

inclusion probability c

for each G

must be known in advance.

A xe d threshold can be use d to draw such a sample. Associate

an independent auxiliary variable

for each item along with a

xed threshold

)

. The item

is included if

< )

. If

is contin-

uous and



is its cumulative distribution function (CDF), then the

probability

is sampled is

? ('

< )

) = 

()

)

. Choosing a thresh-

old such that

= 

()

)

yields a sample from the desired sampling

design. We call the variable

the priority of

and denote the

inclusion of

< )

)

. From this, it is easy to see how

the threshold )

can be used to adjust the inclusion probabilities.

2.2 Sampling challenges and estimation

However, unequal probability sampling can lead to challenges

in sampling and estimation. For example, under memory budget

or sample size constraints, Poisson sampling can violate the con-

straints since there is some non-zero probability that all items are

sampled. It is thus natural to consider samplers that draw xed

size samples. The natural extension of Poisson sampling to xed

sizes is Conditional Poisson Sampling (CPS), which is obtained from

a Poisson Sampling design conditional on the sample size being

exactly

. The Conditional Poisson Sampling design has the attrac-

tive property of being the maximum entropy sampling procedure

for a set of inclusion probabilities. However, there is no ecient

algorithm known for drawing a CPS sample or for computing the

inclusion probabilities [28].

Estimating quantities of interest can be even more problematic.

A sample is almost useless without good estimators. In une qual

probability sampling designs, an unbiased estimate of the popu-

lation total

(

is given by the Hor vitz-Thompson (HT) estimator,

( =

’

(HT)

where

indicates if the item

is included in the sample and

= ?(/

)

is the inclusion probability. This also provides

a solution to the subset sum problem [

] by zeroing any value

that is not in the desired subset. The fundamental problem for

Conditional Poisson sampling and other sampling schemes with

dependence between items’ inclusion is that this dependence makes

inclusion probabilities and good estimators dicult to derive.

If the problem of eciently sampling and computing inclusion

probabilities can be overcome, then it is possible to search for an

optimal sampling design given this estimator. When the inclusion

probabilities

/ G

, each term in the HT estimator is constant.

Furthermore, if the sample size is xed at

, the HT estimator itself

is constant, and thus has minimal variance. A sample that draws

Session 22: Provenance and Uncertainty

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1613

of 14

免费下载

关注

评论