Paper Info
Title
The DLT priority sampling is essentially optimal
Abstract
The priority sampling procedure of N. Duffield, C. Lund and M. Thorup is not only an exciting new approach to sampling weighted data streams, but it has also proven to be highly successful in a variety of practical applications. We resolve the two major issues related to its performance. First we solve the main conjecture of N. Alon, N. Duffield, C. Lund and M. Thorup in [1], which states that the standard deviation for the subset sum estimator obtained from k priority samples is upper bounded by W/√k-1, where W denotes the actual subset sum that the estimator estimates. Although Alon et al. give an O(W/√k-1) upper bound on the standard deviation of the estimator, their formula cannot be used as a performance guarantee in an applied setting, because the constants coming up in their proof are very large. Our constant cannot be improved. We also resolve the conjecture of Duffield, C. Lund and M. Thorup which states that the variance of the priority sampling procedure is not larger than the variance of the threshold sampling procedure with sample size only one smaller. This is the main conjecture in [7]. The conjecture's significance is that the latter procedure is provably optimal within a very general class of sampling algorithms, but unlike priority sampling, it is not practical. Our result therefore certifies that priority sampling offers the unlikely feat of uniting mathematical elegance, (essential) optimality and applicability. Our proof is based on a new integral formula and on very finely tuned telescopic sums.
Year
DOI
Venue
2006
10.1145/1132516.1132539
STOC
Keywords
Field
DocType
n. duffield,k priority sample,priority sampling,latter procedure,standard deviation,c. lund,sampling algorithm,dlt priority sampling,n. alon,m. thorup,main conjecture,upper bound,sample size,internet traffic
Discrete mathematics,Subset sum problem,Combinatorics,Upper and lower bounds,Sampling (statistics),Standard deviation,Conjecture,Gibbs sampling,Mathematics,Estimator,Bounded function
Conference
ISBN
Citations 
PageRank 
1-59593-134-1
25
1.02
References 
Authors
7
1
Name
Order
Citations
PageRank
Mario Szegedy13358325.80