Faster methods for random sampling

ABSTRACT

Several new methods are presented for selecting n records at random without replacement from a file containing N records. Each algorithm selects the records for the sample in a sequential manner—in the same order the records appear in the file. The algorithms are online in that the records for the sample are selected iteratively with no preprocessing. The algorithms require a constant amount of space and are short and easy to implement. The main result of this paper is the design and analysis of Algorithm D, which does the sampling in O(n) time, on the average; roughly n uniform random variates are generated, and approximately n exponentiation operations (of the form ab, for real numbers a and b) are performed during the sampling. This solves an open problem in the literature. CPU timings on a large mainframe computer indicate that Algorithm D is significantly faster than the sampling algorithms in use today.

REFERENCES

• 1: Jon Louis Bentley , James B. Saxe, Generating Sorted Lists of Random Numbers, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.359-364, Sept. 1980 [doi>10.1145/355900.355907]
• 2: Ernvall, J. and Nevalainen, O. An algorithm for unbiased random sampling. Comput. J. 25, 1 (January 1982), 45-47.
• 3: Fan, C.T., Muller, M.E., and Rezucha, I. Development of sampling plans by using sequential (item-by-item) selection techniques and digital computers. Am. Stat. Assn. J. 57 (June 1962), 387-402.
• 4: T. G. Jones, A note on sampling a tape-file, Communications of the ACM, v.5 n.6, p.343, June 1962 [doi>10.1145/367766.368159]
• 5: Kawarasaki, J. and Sibuya, M. Random numbers for simple random sampling without replacement. Keio Math. Sem. Rep No. 7 (1982), 1- 9.
• 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: Lindstrom, E.E. and Vitter, J.S. The design and analysis of BucketSort for bubble memory secondary storage. Tech. Rep. CS-83- 23, Brown University, Providence, RI, (September 1983). See also U.S. Patent Application Provisional Serial No. 500741 (filed June 3, 1983).
• 8: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 9: Vitter, J.S. Random sampling with a reservoir. Tech. Rep. CS-83-17, Brown University, Providence, RI, (July 1983).
• 10: Vitter, J.S. Optimum algorithms for two random sampling problems. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, Tucson, AZ (November 1983), 65-75.

INDEX TERMS

Classification:
  E. Data

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

General Terms:
Algorithms, Design, Performance, Theory