3 ms·
Just curious, dusting off my distant school memories :) How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning? I onc
by willvarfar 2y ago
Just curious, dusting off my distant school memories :)
How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning?
I once had a job at a hospital (back when 'whiz kids' were being hired by pretty much every business) where I used reservoir sampling to make small subsets of records that were stored on DAT tapes.
- michaelmior 2y agoI guess there is a connection in the sense that with reservoir sampling, each sample observed has an equal chance of remaining when you're done. However, if you have duplicates in your samples, traditional algorithms for reservoir sampling do not do anything special with duplicates. So you can end up with duplicates in your output with some probability. I guess maybe it's more interesting to look at the other way. How is the set of samples you're left with at the end of CVM related to the set of samples you get with reservoir sampling?
- _a_a_a_ 2y agoWas wondering the same, thanks for an answer.
- krackers 2y agoKnuth's presentation of this [1] seems very very similar to the heap-version (top-k on a uniform deviate) of reservoir sampling as mentioned in [2]. The difference is in how duplicates are handled. I wouldn't be surprised if this algorithm was in fact already in use somewhere! [1] https://cs.stanford.edu/~knuth/papers/cvm-note.pdf https://cs.stanford.edu/~knuth/papers/cvm-note.pdf [2] https://florian.github.io/reservoir-sampling/ https://florian.github.io/reservoir-sampling/ Edit: Another commenter [3] brought up the BJKST algorithm which seems to be similar procedure except using a suitably "uniform" hash function (pairwise independence) as the deviate instead of a random number. [3] https://news.ycombinator.com/item?id=40389178 https://news.ycombinator.com/item?id=40389178