Sequential reservoir sampling with a nonuniform distribution

ABSTRACT

We present a simple algorithm that allows sampling from a stream of data items without knowing the number of items in advance and without having to store all items in main memory. The sampling distribution may be general, that is, the probability of selecting a data item i may depend on the individual item. The main advantage of the algorithms is that they have to pass through the data items only once to produce a sample of arbitrary size n.We give different variants of the algorithm for sampling with and without replacement and analyze their complexity. We generalize earlier results of Knuth on reservoir sampling with a uniform sampling distribution. The general distribution considered here allows us to sample an item with a probability equal to the relative weight (or fitness) of the data item within the whole set of items. Applications include heuristic optimization procedures such as genetic algorithms where solutions are sampled from a population with probability proportional to their fitness.

REFERENCES

• 1: Devroye, L. 1986. Nonuniform Random Variate Generation. Springer-Verlag, New York, NY.
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: Kim-Hung Li, Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))), ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.481-493, Dec. 1994 [doi>10.1145/198429.198435]
• 5: Reeves, C. 2003. Genetic algorithms. In Handbook of Metaheuristics, F. Glover and G. A. Kochenberger, Eds. Kluwer Academic Publishers, Boston, MA.
• 6: 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.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical software; Random number generation
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Performance, Theory

Keywords:
Genetic algorithms, proportional selection, random sampling, reservoir sampling, roulette wheel simulation, sequential sampling