The interface should be applied to all reservoir sampling algorithms that satisfy strict proportionality between the weights and the inclusion probabilities. Currently, only ChaoSampling has this property. The addition will help determine strictness during runtime and perhaps simplify tests at a later time.

https://doi.org/10.1093/biomet/69.3.653

According to Pareto Sampling versus Sampford and Conditional Poisson Sampling, the parameters of the Pareto sampling design represent inclusion probabilities. Hence, the range of the weights in the Pareto design should be in $(0,1)$. The edge cases of 0 and 1 should not be taken into consideration because they would trivialize the random variates.

Similar to #49.

For example

public static <E> Collection<E> execute(Collection<E> population, int sampleSize, Random random) {
    final LiLSampling<E> sampling = new LiLSampling<>(sampleSize, random);
    sampling.feed(population);
    return sampling.sample;
}

This way, the caller would be able to get the mutable sample collection and not reuse the instance.

Consider changing WeightedRandomSampling.feed(T), WeightedRandomSampling.feed(Iterator<T>) and WeightedRandomSampling.feed(Iterable<T>) to invoke the respective weighted method with some default weight set by the specific implementation instead of the predefined 1.0.

This will be helpful because ParetoSampling doesn't allow 1.0.

WatermanSampling, VitterXSampling and VitterZSampling can overflow long. Inside AbstractRandomSampling streamSize can become Long.MAX_VALUE and it is being increased inside the implementations.

The EfraimidisSampling, ParetoSampling and SequentialPoissonSampling can all be considered order sampling designs. That is sampling designs that setup a floating point key for each element and select the elements with the maximum keys as the sample.

Implement the AbstractOrderSampling class and convert these 3 algorithms as subclasses.

boolean feed(T item)

Returns true if the implementation changed as a result of this call.

boolean feed(Iterable<T> items)

Returns true if the implementation changed as a result of this call.

Need to find an alternative chaining method feed(0).feed(1).feed(2).

It is not reasonable to compare using float comparison inside AbstractOrderSampling:

Instead the comparison should be based on the compareTo method, which also guarantees that no different references return zero.

RandomSampling.sample() already returns a copy and does not mutate the state of the instance. It should probably return a mutable collection instead of an unmodifiable one.

feed(Iterable) can be implemented more efficiently using https://docs.oracle.com/javase/8/docs/api/java/util/RandomAccess.html

In this case, NPE cannot be thrown and null would be allowed.

• K
• L
• M

Li, Kim-Hung. "Reservoir-sampling algorithms of time complexity O (n (1+ log (N/n)))." ACM Transactions on Mathematical Software (TOMS) 20.4 (1994): 481-493.

Which means the constructor and the skipLength and init methods need to be protected.

On EfraimidisSampling and more specifically the line

assert newItem.weight > 0.0 && newItem.weight < 1.0;

sometimes fails because if the weight is too small then 1/weight is too big and the newItem.weight is 0 due to double rounding.

Idea 1

T feed(T item) returns the element T of the reservoir that was replaced by item or null if the sample was not modified as a result of this operation.

Idea 2

A new feed method has to return values from 3 different cases:

1. item was not selected and there was no change in the sample (return null)
2. item was inserted in the sample but nothing was removed (return null?)
3. item replaced an existing item T of the sample (return T)

An obvious solution is to return Optional<T>:

Optional<T> feed(T item) returns null in case (1), an Optional<T> that doesn't hold a value in case (2) and an Optional<T> that holds the reference to the item that was removed in case (3).

The citation links on package-info.java don't work in jitpack, but they would open in the main frame anyway.

Select k elements from a population of n elements without replacement and without rejections in time proportional to k.

The higher order probabilities of all sample tuples must be equal.

RandomSampling.sample() should return a readonly view Iterable or Collection because it would allow it to execute in constant time.

Perhaps rename RandomSampling to ReservoirSampling as well.

Allow more than Integer.MAX_VALUE items to be feeded to a sampler.

• Change RandomSampling.streamSize() to return long instead of int.
• Change the limit that StreamOverflowException is thrown to Long.MAX_VALUE.

The implementation of compareTo in Weighted is not consistent with equals:

In particular, there is no guarantee that System.identityHashCode is unique for every object. Thus, compareTo may return 0 and at the same time equals can return false.

The compareTo method needs to change such that it always returns 0 for same-reference objects and always a non-zero value for different objects, even if they have the same weight.

Each weighted algorithm should have its own default weight because the contract of WeightedRandomSampling doesn't allow for a weight value that is guaranteed to be legal.

Maybe all the feed methods should return the current instance. This will make chain feeding easier.

Add space complexity on

• interfaces
• javadoc
• readme

EfraimidisSampling and ChaoSampling does not rely on the stream size so they shouldn't throw StreamOverflowException.

Reads from stdin and outputs the sample to stdout when stdin is EOF.

Possible interface:

reservoir-sample --tokenization="token_separation_reg_exp" --algorithm="efraimidis" --sample=10 --random-source=file

See the core utility shuf.

Vitter, Jeffrey S. "Random sampling with a reservoir." ACM Transactions on Mathematical Software (TOMS) 11.1 (1985): 37-57.

It is not used anymore and it also goes against the concept of reservoir with the $\mathcal{O}(k)$ memory usage.

It would be nice to have a thread-safe version of at least the best-performing algorithm (Lil). Other than that, very useful, thanks for making this available!

Currently, some or all weighted implementations can receive a NaN weight, which causes a domino effect with weight transformations and probability calculations. NaN (or infinity) should not be an acceptable weight.

• Implement RandomSamplingCollector
• Implement WeightedRandomSamplingCollector
• Add static methods collector() and weightedCollector()
• Add tests
• Add README section on usage

See http://trevershick.github.io/java8/2015/12/02/reservoir-based-sampling.html

On VitterZSampling, avoid performing a NaN check

if (Double.isNaN(this.W)) {
  this.W = Math.pow(random.nextDouble(), -1.0 / sampleSize);
}

on every call of skipLength and initialize W once.

See conversation in #38. Also make the necessary changes to the thread safe version if required.

Create test for ChaoSampling verifying that the probability of inclusion is proportional to the weight.