Consistent Weighted Sampling
Mark S. Manasse, Frank McSherry, Kunal Talwar · 2007
We describe an efficient procedure for sampling representatives from a weighted set such that the probability that for any weightings S and T, the probability that the two choose the same sample is the Jacard similarity: P x min(S(x), T (x)) P r[sample(S) = sample(T)] = P max(S(x), T (x)) The sampling process takes expected time linear in the number of non-zero weights, independent of the weights themselves. We discuss and develop the implementation of our sampling schemes, reducing the requisite computation substantially, and reducing the randomness required to only four bits in expectation.