Stream sampling for variance-optimal estimation of subset sums

ABSTRACT

From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VarOpt_k, that dominates all previous schemes in terms of estimation quality. VarOpt_k provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

REFERENCES

• 1: R. J. Adler, R. E. Feldman, and M. S. Taqqu. A Practical Guide to Heavy Tails. Birkhauser, 1998.
• 2: M. T. Chao. A general purpose unequal probability sampling plan. Biometrika, 69(3):653--656, 1982.
• 3: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Edith Cohen , Haim Kaplan, Bottom-k sketches: better and more efficient estimation of aggregates, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 5: Edith Cohen , Haim Kaplan, Summarizing data using bottom-k sketches, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281133]
• 6: E. Cohen and H. Kaplan. Tighter estimation using bottom-k sketches. In Proceedings of the 34th VLDB Conference, 2008.
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 9: N. G. Duffield, C. Lund, and M. Thorup. Learn more, sample less: control of volume and variance in network measurements. IEEE Transactions on Information Theory, 51(5):1756--1775, 2005.
• 10: Nick Duffield , Carsten Lund , Mikkel Thorup, Priority sampling for estimation of arbitrary subset sums, Journal of the ACM (JACM), v.54 n.6, p.32-es, December 2007 [doi>10.1145/1314690.1314696]
• 11: Pavlos S. Efraimidis , Paul G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters, v.97 n.5, p.181-185, 16 March 2006 [doi>10.1016/j.ipl.2005.11.003]
• 12: C. T. Fan, M. E. Muller, and I. Rezucha. Development of sampling plans by using sequential (item by item) selection techniques and digital computers. J. Amer. Stat. Assoc., 57:387--402, 1962.
• 13: D. G. Horvitz and D. J. Thompson. A generalization of sampling without replacement from a finite universe. J. Amer. Stat. Assoc., 47(260):663--685, 1952.
• 14: Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066159]
• 15: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: David Moore , Vern Paxson , Stefan Savage , Colleen Shannon , Stuart Staniford , Nicholas Weaver, Inside the Slammer Worm, IEEE Security and Privacy, v.1 n.4, p.33-39, July 2003 [doi>10.1109/MSECP.2003.1219056]
• 17: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 18: The Netflix Prize. http://www.netflixprize.com/.
• 19: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.171, October 29-November 01, 1996
• 20: C-E. Särndal, B. Swensson, and J. Wretman. Model Assisted Survey Sampling. Springer, 1992.
• 21: A. Srinivasan, Distributions on Level-Sets with Applications to Approximation Algorithms, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.588, October 14-17, 2001
• 22: Mario Szegedy, The DLT priority sampling is essentially optimal, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132539]
• 23: M. Szegedy and M. Thorup. On the variance of subset sum estimation. In Proc. 15th ESA, LNCS 4698, pages 75--86, 2007.
• 24: Mikkel Thorup, Equivalence between priority queues and sorting, Journal of the ACM (JACM), v.54 n.6, p.28-es, December 2007 [doi>10.1145/1314690.1314692]
• 25: Y. Tillé. An elimination procedure for unequal probability sampling without replacement. Biometrika, 83(1):238--241, 1996.
• 26: Y. Tillé. Sampling Algorithms. 2006.
• 27: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms