Maximally Consistent Sampling and the Jaccard Index of Probability Distributions

Ryan Moulton, Yunjiang Jiang

We introduce simple, efficient algorithms for computing a MinHash of a probability distribution, suitable for both sparse and dense data, with equivalent running times to the state…