A collection of algorithms in Java 8 for the problem of random sampling with a reservoir.
Reservoir sampling is a family of randomized algorithms for randomly choosing a
sample of k items from a list S containing n items, where n is either a
very large or unknown number. Typically n is large enough that the list
doesn't fit into main memory. [1] In this context, the sample of k items will
be referred to as sample and the list S as stream.
This package distinguishes these algorithms into two main categories: the ones
that assign a weight in each item of the source stream and the ones that don't.
These will be referred to as weighted and unweighted random sampling algorithms
respectively. In unweighted algorithms, each item in the stream has probability
k/n in appearing in the sample. In weighted algorithms this probability
depends on the extra parameter weight. Each algorithm may interpret this
parameter in a different way, for example in [2] two possible interpretations
are mentioned.
Random Sampling is published to jcenter. You can add a dependency from your project as follows:
Using Maven
<dependency>
<groupId>gr.james</groupId>
<artifactId>random-sampling</artifactId>
<version>0.16</version>
</dependency>Using Gradle
compile 'gr.james:random-sampling:0.16'
Select 10 numbers at random in the range [1,100]. Each number has a 10% probability of appearing in the sample.
RandomSampling<Integer> rs = new WatermanSampling<>(10, new Random());
rs.feed(IntStream.rangeClosed(1, 100).boxed().iterator());
Collection<Integer> sample = rs.sample();
System.out.println(sample);Select 5 random tokens from an input stream.
RandomSampling<String> rs = new VitterXSampling<>(5, new Random());
rs.feed(new Scanner(System.in));
System.out.println(rs.sample());Same example using Algorithm Z.
RandomSampling<String> rs = new VitterZSampling<>(5, new Random());
rs.feed(new Scanner(System.in));
System.out.println(rs.sample());Select 2 terms from a vocabulary, based on their weight.
WeightedRandomSampling<String> rs = new EfraimidisSampling<>(2, new Random());
rs.feed("collection", 1);
rs.feed("algorithms", 2);
rs.feed("java", 2);
rs.feed("random", 3);
rs.feed("sampling", 4);
rs.feed("reservoir", 5);
System.out.println(rs.sample());Unweighted random sampling using the Java 8 stream API.
RandomSamplingCollector<Integer> collector = WatermanSampling.collector(5, new Random());
Collection<Integer> sample = IntStream.range(0, 20).boxed().collect(collector);
System.out.println(sample);Weighted random sampling using the Java 8 stream API.
WeightedRandomSamplingCollector<String> collector = ChaoSampling.weightedCollector(2, new Random());
Map<String, Double> map = new HashMap<>();
map.put("collection", 1.0);
map.put("algorithms", 2.0);
map.put("java", 2.0);
map.put("random", 3.0);
map.put("sampling", 4.0);
map.put("reservoir", 5.0);
Collection<String> sample = map.entrySet().stream().collect(collector);
System.out.println(sample);| Class | Algorithm | Space | Weighted |
|---|---|---|---|
WatermanSampling |
Algorithm R by Waterman | O(k) |
|
VitterXSampling |
Algorithm X by Vitter | O(k) |
|
VitterZSampling |
Algorithm Z by Vitter | O(k) |
|
LiLSampling |
Algorithm L by Li | O(k) |
|
EfraimidisSampling |
Algorithm A-Res by Efraimidis | O(k) |
✔ |
ChaoSampling |
Algorithm by Chao | O(k) |
✔ |
SequentialPoissonSampling |
Algorithm by Ohlsson | O(k) |
✔ |
ParetoSampling |
Algorithm by Rosén | O(k) |
✔ |
Signature: WatermanSampling implements RandomSampling
- The Art of Computer Programming, Vol II, Random Sampling and Shuffling.
Signature: VitterXSampling implements RandomSampling
Signature: VitterZSampling implements RandomSampling
Signature: LiLSampling implements RandomSampling
Signature: EfraimidisSampling implements WeightedRandomSampling
Signature: ChaoSampling implements WeightedRandomSampling
- Chao, M. T. "A general purpose unequal probability sampling plan." Biometrika 69.3 (1982): 653-656.
- Sugden, R. A. "Chao's list sequential scheme for unequal probability sampling." Journal of Applied Statistics 23.4 (1996): 413-421.
Signature: SequentialPoissonSampling implements WeightedRandomSampling
Signature: ParetoSampling implements WeightedRandomSampling