Title
On the variance of subset sum estimation
Abstract
For high volume data streams and large data warehouses, sampling is used for efficient approximate answers to aggregate queries over selected subsets. We are dealing with a possibly heavy-tailed set of weighted items. We address the question: Which sampling scheme should we use to get the most accurate subset sum estimates? We present a simple theorem on the variance of subset sum estimation and use it to prove optimality and near-optimality of different known sampling schemes. The performance measure suggested in this paper is the average variance over all subsets of any given size. By optimal we mean there is no set of input weights for which any sampling scheme can have a better average variance. For example, we show that appropriately weighted systematic sampling is simultaneously optimal for all subset sizes. More standard schemes such as uniform sampling and probability-proportional-to-size sampling with replacement can be arbitrarily bad. Knowing the variance optimality of different sampling schemes can help deciding which sampling scheme to apply in a given context.
Year
DOI
Venue
2007
10.1007/978-3-540-75520-3_9
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
subset sum estimation,accurate subset sum estimate,average variance,systematic sampling,subset size,variance optimality,uniform sampling,probability-proportional-to-size sampling,different sampling scheme,standard scheme,sampling scheme,data structure
Conference
abs/cs/0702029
ISSN
ISBN
Citations 
0302-9743
3-540-75519-5
11
PageRank 
References 
Authors
0.61
12
2
Name
Order
Citations
PageRank
Mario Szegedy13358325.80
Mikkel Thorup25081366.30