Repository navigation
Alternative to reservoir sketches #298
Description
I recently did a review of the literature and some experiments with reservoir sampling, and found there are lower overhead sampling algorithms equivalent to the implementation of "algorithm R" in this library. I would like to contribute the best performing implementation to the library.
I have a few questions
- does this library need another reservoir sketch and is it likely to accept one? That is, is preparing a patch a worthwhile use of my time?
- Is my testing strategy agreeable? If not, what kind of tests would I need to provide? My strategy is:
- generate input data from a known parametric distribution
- sort the data to introduce sequential bias which must not be evident in the sample
- take a sample
- evaluate the maximum likelihood estimator over the sample to check I recover the distribution parameters within some tolerance.
- is it better to replace or to complement
ReservoirLongsSketch/ReservoirItemsSketch?
Activity
jmalkin commentedon Jan 31, 2020
We're always interested in improved algorithms. The key question is whether the alternatives are properly mergeable, especially across different reservoir sizes.
I know there are some stand-alone improvements that could be made, for instance (from memory discussing this several year sago) you can pre-compute how many items you'll skip before the next acceptance and avoid calling the random number generator each time. But validly merging the sampling state in that case is ... hard.
We know that merging only preserves first-order probabilities (there's a uniform likelihood of inclusion for each item, but there can be correlations between item pairs). Since there isn't a (known?) way around that, that's ok. But mergeability is considered a key property for the library. Error bounds, too, but if the rest of the algo is valid that shouldn't matter here.
So before writing new code, can we check that the alternatives can be merged? If yes, we can continue the discussion on how best to validate that and get it included. Replace vs complement comes down to things like whether there's a compatible way to migrate previously serialized binary images.
leerho commentedon Jan 31, 2020
Richard, it would also be helpful if you could give us a reference to the paper about the algorithm you are considering.
richardstartin commentedon Feb 2, 2020
@jmalkin actually the idea behind the algorithms is of generating the number of elements to skip
srather than doing so implicitly bysfailed trials, exactly as you mention, and I had not considered mergeability at all. There having been a previous discussion resulting in using algorithm R for the sake of mergeability gives me second thoughts about preparing a contribution.@leerho I read Vitter's paper on reservoir sampling. I wrote up my notes on the paper here, and have implementations here, which show that the algorithms produce similar samples, and that the overhead of R is significant relative to X and Z when the work to produce the sampled value is cheap.
leerho commentedon Mar 5, 2020
Thank you for your thoughtful consideration of a contribution. We have recently added a page for potential contributors, such as yourself, to help communicate what criteria we are currently using for new sketch contributions into the library. Nevertheless, we are always open to suggestions!
Sketch Criteria
jmalkin commentedon Mar 24, 2025
At this point, I believe we have an improved merge option (see #647) that would work with this approach. But my initial testing in octave is showing consistent discrepancies between algorithms judging by the cumulative number of samples selected by item n (averaged across many trials, obviously, since a single run won't say much).
Since I know the original, slower algo's probabilities are correct I'm considering that a baseline and am wary of deviating from that -- and especially, as here, deviations that seem to slowly grow over time. But I'll document it in the other issue.