# Maximally Consistent Sampling and the Jaccard Index of Probability Distributions

arXiv: https://arxiv.org/abs/1809.04052 · HTML: https://mlsanity.com/paper/1809.04052/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2018.

## Built on by (most cited first, 3 of 3)

- [Jaccard Metric Losses: Optimizing the Jaccard Index with Soft Labels](https://mlsanity.com/paper/2302.05666/) (2023)
- [Stars: Tera-Scale Graph Building for Clustering and Graph Learning](https://mlsanity.com/paper/2212.02635/) (2022)
- [Fast Gumbel-Max Sketch and its Applications](https://mlsanity.com/paper/2302.05176/) (2023)

## Abstract (arXiv)

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 of the art for both cases. The collision probability of these algorithms is a new measure of the similarity of positive vectors which we investigate in detail. We describe the sense in which this collision probability is optimal for any Locality Sensitive Hash based on sampling. We argue that this similarity measure is more useful for probability distributions than the similarity pursued by other algorithms for weighted MinHash, and is the natural generalization of the Jaccard index.