The method selects top-K values using log-uniform variables.
TL;DR: Reservoir sampling.
Given a sequence of positive real numbers q(1), q(2), ... and u(1), u(2) iid uniform [0, 1], then, for any n, the indexes of the top-K
log(u(k))/q(k)
in { 1 ... n } are distributed as independent p ∝ q(k) without replacement.
Users praise the reservoir sampling method using log-uniform weights as a neat and useful trick for streaming systems without full-history rescoring.
No Digg Deeper questions have been answered for this story yet.
@francoisfleuret Used to be the culmination of one of my interview questions. Such a neat algorithm!
TL;DR: Reservoir sampling.
Given a sequence of positive real numbers q(1), q(2), ... and u(1), u(2) iid uniform [0, 1], then, for any n, the indexes of the top-K
log(u(k))/q(k)
in { 1 ... n } are distributed as independent p ∝ q(k) without replacement.
@francoisfleuret this is the Gumbel-top-K trick!
@francoisfleuret This trick is so useful in streaming systems. No full-history rescoring.
@francoisfleuret https://samwho.dev/reservoir-sampling/ a neat explanation here