Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n)))

ABSTRACT

One-pass algorithms for sampling n records without replacement from a population of unknown size n are known as reservoir-sampling algorithms. In this article, Vitter's reservoir-sampling algorithm, algorithm Z, is modified to give a more efficient algorithm, algorithm K. Additionally, two new algorithms, algorithm L and algorithm M, are proposed. If the time for scanning the population is ignored, all the four algorithms have expected CPU time O(n(1 + log(N/n))), which is optimum up to a constant factor. Expressions of the expected CPU time for the algorithms are presented. Among the four, algorithm L is the simplest, and algorithm M is the most efficient when n and N/n are large and N is O(n2).

REFERENCES

• 1: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 2: R. C. H. Cheng, Generating beta variates with nonintegral shape parameters, Communications of the ACM, v.21 n.4, p.317-322, April 1978 [doi>10.1145/359460.359482]
• 3: DEVROYE, L. 1986. Non-uniform Random Variate Generation. Springer-Verlag, New York.
• 4: FAN, C. T., MULLER, M. E., ANn REZUCHA, I. 1962. Development of sampling plans by using sequential (item by item) selection techniques and digital computers. Am. Stat. Assoc. J. 57, 298 (June), 387-402.
• 5: IMSL. 1987. IMSL Stat/Library, User's Manual. IMSL, Inc., Houston, Tex.
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 8: LI, K.-H. 1992a.. Reservoir sampling algorithms. I. Analysis and modification of Vitter's algorithm Z. Tech. Rep. No. 92.2, Dept. of Statistics, The Chinese Univ. of Hong Kong, Shatin, N.T., Hong Kong.
• 9: LL K.-H. 1992b. Reservoir sampling algorithms. II. New algorithms. Tech. Rep. No. 92.3, Dept. of Statistics, The Chinese Univ. of Hong Kong, Shatin, N.T., Hong Kong.
• 10: McLEOD, A. I. AND BELLHOUSE, D. R. 1983. A convenient algorithm for drawing a simple random sample. Appl. Stat. 32, 2, 182-184.
• 11: PIN~C4AM, R.S. 1987. An efficient algorithm for drawing a simple random sample. Appl. Stat. 36, 3, 370-372.
• 12: 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:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation; Statistical software; Probabilistic algorithms (including Monte Carlo)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Algorithms, Performance, Theory

Keywords:
analysis of algorithms, random sampling, reservoir