The DLT priority sampling is essentially optimal

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

29 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationSTOC'06
Subtitle of host publicationProceedings of the 38th Annual ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery (ACM)
Pages150-158
Number of pages9
ISBN (Print)1595931341, 9781595931344
DOIs
StatePublished - 2006
Event38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States
Duration: May 21 2006May 23 2006

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume2006
ISSN (Print)0737-8017

Other

Other38th Annual ACM Symposium on Theory of Computing, STOC'06
Country/TerritoryUnited States
CitySeattle, WA
Period5/21/065/23/06

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Integral formula
  • Internet traffic
  • Network measurement
  • Priority sampling
  • Subset sum estimate
  • Telescopic sums

Fingerprint

Dive into the research topics of 'The DLT priority sampling is essentially optimal'. Together they form a unique fingerprint.

Cite this