Semantic MinHash: Bringing MinHash to Embeddings

MinHash and locality-sensitive hashing (LSH) provide reusable signatures and bucket-based candidate generation for set similarity, but classical set MinHash does not directly capture the semantic geometry of dense embeddings. We present Semantic MinHash (\method), which constructs a distance-annotated set for each embedding using shared sampled references and takes the minimum-distance index directly as its hash value. Repeated selections produce a discrete signature that brings the MinHash processing pattern to embedding retrieval, similarity graphs and duplicate screening. Building on nearest-reference winner-take-all selection, we derive an exact finite-reference collision law with shared-order ties, conditional locality and candidate-precision guarantees, and a maximum-load bound based on reference coverage and concentration. Experiments on text, image and multimodal embeddings demonstrate selective candidate generation: data references reduce mean candidate fractions on eight datasets against an equally tuned spherical-reference control, while semantic screening and complete-task comparisons establish practical benefits at the evaluated operating points. These results connect embedding-to-set construction, collision analysis and empirical task performance, providing a common basis for applying minimum-index signatures and LSH to semantic embeddings.