On the variance of subset sum estimation

Mario Szegedy, Mikkel Thorup

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540755197
StatePublished - 2007
Event15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel
Duration: Oct 8 2007Oct 10 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4698 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other15th Annual European Symposium on Algorithms, ESA 2007

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the variance of subset sum estimation'. Together they form a unique fingerprint.

Cite this