Reservior sampling using a heap. Both weighted and unweighted random sampling are
supported.
The algorithm used here is based on the one-pass algorithm described by Pavlos
Efraimidis and Paul Spirakis ("Weighted Random Sampling over Data Streams", Pavlos S.
Efraimidis, https://arxiv.org/abs/1012.0256). In the unweighted case weights are
simply set to one.
The implementation uses a heap (priority queue) large enough to hold the desired
number of lines. Input is read line-by-line, assigned a random value, and added to
the heap. The role of the identify the lines with the highest assigned random
values. Once the heap is full, adding a new line means dropping the line with the
lowest score. A "min" heap used for this reason.
When done reading all lines, the "min" heap is in the opposite order needed for
output. The desired order is obtained by removing each element one at at time from
the heap. The underlying data store will have the elements in correct order.
Generating output in weighted order matters for several reasons:
- For weighted sampling, it preserves the property that smaller valid subsets can be
created by taking the first N lines.
- For unweighted sampling, it ensures that all output permutations are possible, and
are not influences by input order or the heap data structure used.
- Order consistency when making repeated use of the same random seeds, but with
different sample sizes.
There are use cases where only the selection set matters, for these some performance
could be gained by skipping the reordering and simply printing the backing store
array in-order, but making this distinction seems an unnecessary complication.
Notes:
- In tsv-sample versions 1.2.1 and earlier this routine also supported randomization
of all input lines. This was dropped in version 1.2.2 in favor of the approach
used in randomizeLines. The latter has significant advantages given that all data
data must be read into memory.
- For larger reservoir sizes better performance can be achieved by using
reservoirSamplingAlgorithmR. See the documentation for that function for details.
Reservior sampling using a heap. Both weighted and unweighted random sampling are supported.
The algorithm used here is based on the one-pass algorithm described by Pavlos Efraimidis and Paul Spirakis ("Weighted Random Sampling over Data Streams", Pavlos S. Efraimidis, https://arxiv.org/abs/1012.0256). In the unweighted case weights are simply set to one.
The implementation uses a heap (priority queue) large enough to hold the desired number of lines. Input is read line-by-line, assigned a random value, and added to the heap. The role of the identify the lines with the highest assigned random values. Once the heap is full, adding a new line means dropping the line with the lowest score. A "min" heap used for this reason.
When done reading all lines, the "min" heap is in the opposite order needed for output. The desired order is obtained by removing each element one at at time from the heap. The underlying data store will have the elements in correct order.
Generating output in weighted order matters for several reasons: - For weighted sampling, it preserves the property that smaller valid subsets can be created by taking the first N lines. - For unweighted sampling, it ensures that all output permutations are possible, and are not influences by input order or the heap data structure used. - Order consistency when making repeated use of the same random seeds, but with different sample sizes.
There are use cases where only the selection set matters, for these some performance could be gained by skipping the reordering and simply printing the backing store array in-order, but making this distinction seems an unnecessary complication.
Notes: - In tsv-sample versions 1.2.1 and earlier this routine also supported randomization of all input lines. This was dropped in version 1.2.2 in favor of the approach used in randomizeLines. The latter has significant advantages given that all data data must be read into memory. - For larger reservoir sizes better performance can be achieved by using reservoirSamplingAlgorithmR. See the documentation for that function for details.