Research map / Learning theory and algorithms / Prediction and decision losses
Optimal Densification for Fast and Accurate Minwise Hashing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tailored 2-universal reassignment instead of improved densification (h+) | Optimal densification (h*) · Jaccard similarity estimation on word-vector pairs | MSE | Helped |
| Use optimal densification rather than improved densification (h+) | RCV1 · RCV1 | runtime (ms), 300 hashes: 104 -> 116 | Mixed |
| Use optimal densification rather than improved densification (h+) | URL · URL | runtime (ms), 300 hashes: 624 -> 631 | Mixed |
| Use optimal densification rather than improved densification (h+) | NEWS20 · NEWS20 | runtime (ms), 300 hashes: 205 -> 174 | Helped |
| Use optimal densification rather than vanilla MinHash | RCV1 · RCV1 | runtime (ms), 300 hashes: 1098 -> 116 | Helped |
| Use optimal densification rather than vanilla MinHash | URL · URL | runtime (ms), 300 hashes: 8158 -> 631 | Helped |
| Use optimal densification rather than vanilla MinHash | NEWS20 · NEWS20 | runtime (ms), 300 hashes: 3650 -> 174 | Helped |
| Use optimal densification as the number of hashes increases | Optimal densification (h*) · Jaccard similarity estimation | variance | Helped |
| Increase the number of hashes for existing densification schemes | Densification (h) and improved densification (h+) · Jaccard similarity estimation | variance | No clear effect |
| Use simple 2-universal hashing for reassignment, without attempt-indexed hashing (ablation) | Densification · Jaccard similarity estimation | variance | Hurt |
| Add random bits to nearest-bin reassignment (ablation) | Improved densification (h+) · Jaccard similarity estimation | variance | Helped |
Closest papers by meaning
- Re-randomized Densification for One Permutation Hashing and Bin-wise Consistent Weighted Sampling (NeurIPS 2019 · similarity 0.90)
- Simple and Efficient Weighted Minwise Hashing (NeurIPS 2016 · similarity 0.89)
- C-MinHash: Improving Minwise Hashing with Circulant Permutation (ICML 2022 · similarity 0.88)
- Learning to Hash Robustly, Guaranteed (ICML 2022 · similarity 0.88)
- Fully Understanding The Hashing Trick (NeurIPS 2018 · similarity 0.86)
- Sublinear Time Nearest Neighbor Search over Generalized Weighted Space (ICML 2019 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.