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.

REFERENCES

• 1: N. Alon, N. Duffield, C. Lund, and M. Thorup. Estimating sums of arbitrary selections with few probes. PODS, pages 317--325, 2005.
• 2: K.R.W. Brewer and M. Hanif. Sampling with unequal probabilities. Springer-Verlag, 1983.
• 3: Chaudhuri, R. Motwani, and V. Narasayya. On random sampling over joins. pages 263--274, 1999.
• 4: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534 ]
• 5: Nick G. Duffield, Carsten Lund, and Mikkel Thorup. Estimating ow distributions from sampled ow statistics. SIGCOMM, pages 325--336, 2003.
• 6: Nick G. Duffield, Carsten Lund, and Mikkel Thorup. Learn more, sample less: control of volume and variance in network measurement. IEEE Transactions in Information Theory, 51(5):1756--1775, 2005.
• 7: Nick G. Duffield, Carsten Lund, and Mikkel Thorup. Sampling to estimate arbitrary subset sums. arXiv.org:cs/0509026, 2005.
• 8: Joseph M. Hellerstein, Peter J. Haas, and Helen J. Wang. Online aggregation. pages 171--182, 1997.
• 9: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 10: Nicholas C. Weaver. The spread of the sapphire/slammer worm. Web page.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
Internet traffic, integral formula, network measurement, priority sampling, subset sum estimate, telescopic sums