Maximally Consistent Sampling and the Jaccard Index of Probability Distributions
Ryan Moulton, Yunjiang Jiang
cs.DS, cs.IR
2018-09-12
P-MinHash collides with scale-invariant J_P, Pareto-optimal among sampling LSHs. On web unigrams, 64 hashes match 128 weighted MinHashes for retrieving pairs with JSD<0.25.
MinHash is the workhorse for large-scale dedup and near-neighbor lookup: under a random permutation, two sets share a minimum element with probability equal to Jaccard. Weighted objects got two recipes from Chum et al. One attaches a global weight per element, fine for idf. The other hashes positive vectors with collision probability JW = Σ min(xi,yi) / Σ max(xi,yi). Later work made the second recipe handle arbitrary positive weights at Ioffe and Shrivastava speed. The target collision probability stayed JW.
JW is a poor similarity for probability distributions. It is not scale-invariant. Normalize two sets into uniforms and JW drops below set Jaccard when the cardinalities differ. It is blind to support changes: JW((a,b,c,0),(a,b,0,c)) equals JW((a+c,b),(a,b+c)), while information-theoretic scores treat mismatched support as worst-case. Switching a running unweighted MinHash system onto JW also lowers collisions across the board, so hash counts and concatenations tuned for Jaccard stop lining up.
A drop-in Jaccard for distributions should be scale-invariant, no lower than set Jaccard on uniforms, sensitive to support, and realizable as a collision probability.
P-MinHash starts from Chum's first algorithm and extends it to any positive vector. For each nonzero coordinate i, draw ei = −log Ui / xi and emit argmini ei. Exponential racing: the chance of picking i is proportional to xi. The same hash seed on x and y collides with probability
JP(x,y) = Σ{i: xi,yi>0} 1 / Σj max(xj/xi, yj/yi).
H(αx)=H(x), so the score ignores scale. Geometrically, cut the simplex according to x and pin the same random point in every cell; the shared face-volume is JP.
Sparse data scans nonzeros in linear time, matching Ioffe 2010. Dense or continuous data feeds the same exponentials into A Sampling's Global-Bound algorithm, sharing a sorted hash prefix. Runtime matches Shrivastava 2016 on dense weighted MinHash and also covers continuous measures.
JP is Pareto-optimal among sampling LSHs: beat it on one pair and you must lose collisions on a closer pair. JW is dominated. If JW=(1−p)/(1+p), then that value ≤ JP ≤ 1−p, and both ends are tight. 1−JP is a metric on the simplex.
The experiment uses normalized unigram vectors from 6.6 billion high-PageRank pages. Pairs were importance-sampled with a sum of two W-MinHashes, 100 million pairs scored, then inverse-weighted to mimic all nonzero pairs.
JP tracks Jensen-Shannon divergence much more tightly than JW. About 10^{−7} of pairs fall below their approximate JP lower curve, at most 0.0077 under; JW puts 7×10^{−3} of pairs under the same curve, up to 0.16 under. Against set Jaccard, log(JP/Jaccard) sits near zero; log(JW/Jaccard) sits below, as the uniform-distribution theory predicts.
In a key-value store, AND (summing hashes into one key) is almost free; OR (emitting extra independent keys) costs linear storage and CPU. Higher collision probability makes high recall cheaper. Retrieving pairs with JSD<0.25, P-MinHash at 64 hashes matches W-MinHash at 128. At low cost it even slightly wins at retrieving JW>0.5 pairs, the task W-MinHash was built for: on pairs already high under JW, JP is higher still, and squaring two hashes behaves like one-hash recall with two-hash precision. At higher cost, JW overtakes once the score gap itself dominates.
If the objects are topic distributions, image histograms, or page term distributions, keeping JW as the MinHash collision probability means approximating an information-theoretic distance with a scale-variant set weight. P-MinHash puts a JSD-like quantity in the collision, at then-SOTA cost on both sparse and dense data, and the 64-versus-128 curve is real money in inverted indexes and KV stores. Migrating from unweighted MinHash, JP also sits closer to the original Jaccard, so hash budgets need less retuning.
This is ICDMW 2018. The algorithm does not need a sequel to be usable. Use it when inputs should be treated as distributions. If they are weighted multisets, JW remains the right target.
The nested-max formula is O(n^2) if transcribed literally; sorting on xi/yi brings it to O(n log n). Pareto optimality is not "highest on every pair": a tree of recursive samples can push collisions on one index to min(xi,yi) by sacrificing others. The web experiment's proposal distribution is itself W-MinHash, so coverage of extremely dissimilar pairs follows that proposal. The JP–JSD lower curve is a numerical Euler-Lagrange approximation, not a theorem; 10^{−7} of pairs still breach it. Continuous JP is an infimum over finite partitions; singular measures and mutually singular supports need care. There is no public code appendix. For modern vector search this is LSH for high-dimensional sparse counts and distributions, not ANN for dense embeddings.