Sampling collision probability is provably optimal for LSH, revisits 2018 MinHash paper
moultano · x · 2026-09-06
Google researcher Ryan Moulton pointed to his 2018 paper "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions" (arXiv:1809.04052, ICDMW 2018) to answer a question about optimality: if you sample from a distribution to maximize the probability of colliding with another unknown distribution, the paper's algorithm is optimal in a strong sense.
Key contributions:
- Simple, efficient algorithms for computing a MinHash of a probability distribution, matching state-of-the-art running times for both sparse and dense data
- The collision probability of these algorithms defines a new similarity measure for positive vectors — the natural generalization of the Jaccard index to probability distributions
- The paper proves this collision probability is the optimal similarity achievable by any sampling-based locality sensitive hash
More from Research
- MatBrain splits reasoning from tool use: two models screen 30,000 crystal candidates in 48 hours — bravo_abad · 2026-09-23
- Scale AI launches SWE-Bench Pro V2, a harder agentic coding benchmark — bigblueboo · 2026-09-23
- If AI Writes All the Papers, Peer Review Becomes Humanity's Remaining Role — sudoraohacker · 2026-09-23
- Yarin Gal: I Ignore Papers Where the Candidate Isn't First or Last Author — yaringal · 2026-09-23
- New paper: Transferring the Intelligence of VLMs to Robotic Control — _akhaliq · 2026-09-23
- NTU UMM study: generation training boosts understanding in native multimodal models, but naive sharing conflicts — jiqizhixin · 2026-09-23