File RandomSampling.h

↰ Parent directory (ADS/numeric)

The uniform sampling of n of N items, chapter 3 of the notes, in the three settings there: the items on the disk with N known, a stream with N known, a stream with N unknown.

Definition (ADS/numeric/RandomSampling.h)

Detailed Description

The samplings of positions return them sorted, so that the items are then read by one pass, at most :math:` min{ n , lceil N / B rceil } ` I/Os [see DiskReader::at() of File TwoLevelMemory.h].

  • sampleBySwaps() is Algorithm 3.1, the first n steps of the shuffle of Fisher and Yates [see shuffle() of File RandomNumbers.h] on an array of the N positions: n random numbers, but :math:` Theta( N ) ` space and up to n random I/Os.

  • sampleByDictionary() is Algorithm 3.2: random positions kept in a hash table, the repeated ones drawn again; with :math:` n leq N / 2 ` a draw repeats with probability below 1/2, hence O( n ) expected time and space (Fact 3.1), and for n > N / 2 the N - n positions left out are drawn instead.

  • sampleBySorting() is Algorithm 3.3 with the bucket sort of Fact 3.3: n random positions sorted by n buckets of width :math:` lceil N / n rceil , O( 1 ) expected items each, sorted by insertion [see :ref:`file_ADS_sort_InsertionSort.h], and the repetitions removed; the positions missing are drawn again and merged, instead of all n as in the notes, which is the same distribution (the process is symmetric in the N positions) but needs no luck when n exceeds :math:` sqrt{N} ` and the birthday paradox makes a repetition likely, :math:` 1 - e^{-n ( n - 1 ) / 2 N} `; for n > N / 2 the positions left out are drawn, as above.

  • Algorithm 3.4, one pass that selects position j with probability :math:` ( n - s ) / ( N - j ) , s the positions already selected, is selectionSampling() of :ref:`file_ADS_numeric_RandomNumbers.h (Algorithm S of Knuth), N random numbers. sampleBySkips() is the method of Vitter that draws the gaps instead, :math:` P( G = g ) = binom{V - g - 1}{v - 1} / binom{V}{v} ` for v positions still to select among V: Algorithm D, by rejection with a continuous envelope, about n random numbers and O( n ) expected time, falling back to Algorithm A (the gap by the sequential search of its distribution, O( N ) time but n random numbers) once n exceeds N / 13, where A is faster.

  • heapSampling() is Algorithm 3.5 for a stream of unknown length: a random key per item, the n largest keys kept in a heap [see File DaryHeap.h], :math:` O( N log n ) ` time; reservoirSampling() of File RandomNumbers.h is Algorithm 3.6 (Algorithm R of Knuth), O( N ) time and exactly n items of space, optimal in this model.

  • reservoirSampleL() is Algorithm L of Li, beyond the notes, the reservoir for a stream of unknown length that draws the number of items to skip instead of a number per item: with a uniform key per item, the reservoir holds the n items of the smallest keys, and W, the largest of them, is distributed as a product of n-th roots of uniforms, :math:` W leftarrow W U^{1/n} ` at each entry; the next item whose key is below W comes after a geometric number of items, :math:` S = lfloor ln U’ / ln( 1 - W ) rfloor , :math: P( S = s ) = ( 1 - W )^s W , and replaces a uniform item of the reservoir. The item t > n enters with probability n / t, so that :math: n ( H_N - H_n ) approx n ln( N / n ) ` items enter, each for 3 random numbers: :math:` O( n ( 1 + log( N / n ) ) ) ` of them in all and, on a random access range, as much time, the skipped items never touched.

Compared with the literature: Vitter’s Algorithm D is the method of choice when N is known, Algorithm Z of the same author does the same for the reservoir as Algorithm L, with a rejection that is more complex and no faster, and the random keys of heapSampling() are the start of the weighted sampling of Efraimidis and Spirakis, where the key of an item of weight w is :math:` U^{1 / w} `.

The contracts [see File Contract.h]: n <= N; the positions are distinct, below N and sorted, an audit. The functions are defined in RandomSampling.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 3

    1. Vitter, Faster methods for random sampling, Communications of the ACM 27(7), 703-718, 1984, doi:10.1145/358105.893

    1. Vitter, An efficient algorithm for sequential random sampling, ACM Transactions on Mathematical Software 13(1), 58-67, 1987, doi:10.1145/23002.23003

    1. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software 11(1), 37-57, 1985, doi:10.1145/3147.3165

K.-H. Li, Reservoir-sampling algorithms of time complexity O( n ( 1 + log( N / n ) ) ), ACM Transactions on Mathematical Software 20(4), 481-493, 1994, doi:10.1145/198429.198435

    1. Efraimidis, P. G. Spirakis, Weighted random sampling with a reservoir, Information Processing Letters 97(5), 181-185, 2006, doi:10.1016/j.ipl.2005.11.003

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions