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. MinHashing BID0 is a popular Locality Sensitive Hashing algorithm for clustering and retrieval on large datasets. Its extreme simplicity and efficiency, as well as its natural pairing with MapReduce and key-value datastores, have made it a basic building block in many domains, particularly document clustering BID0 BID1 and graph clustering BID2 BID3 .Given a finite set U , and a uniformly random permutation π, the map X → arg min i∈X π(i) provides a representation of any subset X of U that is stable under small changes to X. If X, Y are both subsets of U the well-known Jaccard index BID4 Practically, this random permutation is generated by applying some hash function to each i with a fixed random seed, hence "MinHashing."In order to hash objects other than sets, Chum et al. BID5 introduced two algorithms for incorporating weights in the computation of MinHashes. The first algorithm associates constant global weights with the set members, suitable for idf weighting. The collision probability that results is ∑ i∈X∩Y wi ∑ i∈X∪Y wi . The second algorithm computesMinHashes of vectors of positive integers, yielding a collision probability of J W (x, y) = ∑ i min (x i , y i ) ∑ i max (x i , y i ) Subsequent work BID6 [8] BID8 has improved the efficiency of the second algorithm and extended it to arbitrary positive weights, while still achieving J W as the collision probability.J W is one of several generalizations of the Jaccard index to non-negative vectors. It is useful because it is monotonic with respect to the L 1 distance between x and y when they are both L 1 normalized, but it is unnatural in many ways for probability distributions.If we convert sets to binary vectors x, y, with x i , y i ∈ {0, 1}, then J W (x, y) = J(X, Y ). But if we convert these vectors to probability distributions by normalizing them so that x i ∈ { 0, As a consequence, switching a system from an unweighted MinHash to a MinHash based on J W will generally decrease the collision probabilities. Furthermore, J W is insensitive to important differences between probability distributions. It counts all differences on an element in the same linear scale regardless of the mass the distributions share on that element. For instance, J W ((a, b, c, 0) , (a, b, 0, c)) = J W ((a + c, b), (a, b + c)). This makes it a poor choice when the ultimate goal is to measure similarity using an expression based in information-theory or likelihood where having differing support typically results in the worst possible score.For a drop-in replacement for the Jaccard index that treats its input as a probability distribution, we'd like it to have the following properties. We've described a new generalization of the Jaccard index, and shown several qualities that motivate it as the natural extension to probability distributions. In particular, we proved that it is optimal on all distributions in the same sense that the Jaccard index is optimal on uniform distributions. We've demonstrated its utility by showing J P 's similarity in practice to the Jensen-Shannon divergence, a popular clustering criterion. We've described two MinHashing algorithms that achieve this as their collision probability with equivalent running time to the state of the art on both sparse and dense data.
The minimum of a set of exponentially distributed hashes has a very useful collision probability that generalizes the Jaccard Index to probability distributions.
{"src": "scitldr-AIC_train", "paper_id": "BkOswnc5z"}