# DartMinHash: Fast Sketching for Weighted Sets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2020.

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

- [Coupling without Communication and Drafter-Invariant Speculative Decoding](https://mlsanity.com/paper/2408.07978/) (2024)

## Abstract (arXiv)

Weighted minwise hashing is a standard dimensionality reduction technique with applications to similarity search and large-scale kernel machines. We introduce a simple algorithm that takes a weighted set x ∈ ℝ≥ 0d and computes k independent minhashes in expected time O(k log k + Vert x Vert0log( Vert x Vert1 + 1/Vert x Vert1)), improving upon the state-of-the-art BagMinHash algorithm (KDD '18) and representing the fastest weighted minhash algorithm for sparse data. Our experiments show running times that scale better with k and Vert x Vert0 compared to ICWS (ICDM '10) and BagMinhash, obtaining 10x speedups in common use cases. Our approach also gives rise to a technique for computing fully independent locality-sensitive hash values for (L, K)-parameterized approximate near neighbor search under weighted Jaccard similarity in optimal expected time O(LK + Vert x Vert0), improving on prior work even in the case of unweighted sets.