Incomplete example implementation of naive reservoir sampling algorithm

[dyladan]

In exemplar defaults the SimpleExemplarReservoir is defined as:

SimpleExemplarReservoir This Exemplar reservoir MAY take a configuration parameter for the size of the reservoir pool. The reservoir will accept measurements using an equivalent of the naive reservoir sampling algorithm

bucket = random_integer(0, num_measurements_seen)
if bucket < num_buckets then
 reservoir[bucket] = measurement
end

Reading the article, it seems like the implementation given here is incorrect or at least incomplete. For the first n elements where n is the size of the reservoir the exemplar should be offered to bucket n-1. Only after the reservoir is full should exemplars be sampled by generating the random number.

A more complete example might be:

bucket = num_measurements_seen if num_measurements_seen < reservoir.size else random_integer(0, num_measurements_seen)
if bucket < num_buckets then
	reservoir[bucket] = measurement
end

[jsuereth]

This is a good call out, by simplification was, partially, on purpose, assuming high-load on measurements. However, the version you list is better for low-volume instruments. We should update the example.

In practice, the important aspect of this sampler is that the likelihood of sampling changes as more measurement are seen.