# Fast Gumbel-Max Sketch and its Applications

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 61 references that are in the map.
- First posted on arXiv 10 Feb 2023.

## Builds on (most cited first, 12 of 12)

- [A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration](https://mlsanity.com/paper/2101.01507/) (2021)
- [Optimal Densification for Fast and Accurate Minwise Hashing](https://mlsanity.com/paper/1703.04664/) (2017)
- [Improved Densification of One Permutation Hashing](https://mlsanity.com/paper/1406.4784/) (2014)
- [A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets](https://mlsanity.com/paper/1905.08977/) (2019)
- [Consistent Weighted Sampling Made Fast, Small, and Easy](https://mlsanity.com/paper/1410.4266/) (2014)
- [New cardinality estimation algorithms for HyperLogLog sketches](https://mlsanity.com/paper/1702.01284/) (2017)
- [Improved Consistent Weighted Sampling Revisited](https://mlsanity.com/paper/1706.01172/) (2017)
- [BagMinHash - Minwise Hashing Algorithm for Weighted Sets](https://mlsanity.com/paper/1802.03914/) (2018)
- [Maximally Consistent Sampling and the Jaccard Index of Probability Distributions](https://mlsanity.com/paper/1809.04052/) (2018)
- [Fast Generating A Large Number of Gumbel-Max Variables](https://mlsanity.com/paper/2002.00413/) (2020)
- [Fast Similarity Sketching](https://mlsanity.com/paper/1704.04370/) (2017)
- [Utilizing Dynamic Properties of Sharing Bits and Registers to Estimate User Cardinalities over Time](https://mlsanity.com/paper/1811.09126/) (2018)

## Abstract (arXiv)

The well-known Gumbel-Max Trick for sampling elements from a categorical distribution (or more generally a non-negative vector) and its variants have been widely used in areas such as machine learning and information retrieval. To sample a random element i in proportion to its positive weight vi, the Gumbel-Max Trick first computes a Gumbel random variable gi for each positive weight element i, and then samples the element i with the largest value of gi+ln vi. Recently, applications including similarity estimation and weighted cardinality estimation require to generate k independent Gumbel-Max variables from high dimensional vectors. However, it is computationally expensive for a large k (e.g., hundreds or even thousands) when using the traditional Gumbel-Max Trick. To solve this problem, we propose a novel algorithm, FastGM, which reduces the time complexity from O(kn^+) to O(k ln k + n^+), where n^+ is the number of positive elements in the vector of interest. FastGM stops the procedure of Gumbel random variables computing for many elements, especially for those with small weights. We perform experiments on a variety of real-world datasets and the experimental results demonstrate that FastGM is orders of magnitude faster than state-of-the-art methods without sacrificing accuracy or incurring additional expenses.