Consistent Sampling with Replacement. (arXiv:1808.10016v1 [cs.DS])

We describe a very simple method for `consistent sampling' that allows for sampling with replacement. The method extends previous approaches to consistent sampling, which assign a pseudorandom real number to each element, and sample those with the smallest associated numbers. When sampling with replacement, our extension gives the item sampled a new, larger, associated pseudorandom number, and returns it to the pool of items being sampled.

from cs updates on arXiv.org https://ift.tt/2N5wzgr
//