Fast Gumbel-Max Sketch and its Applications

Yuanming Zhang, Pinghui Wang, Yiyan Qi, Kuankuan Cheng, Junzhou Zhao, Guangjian Tian, Xiaohong Guan

Introduction

The Gumbel-Max Trick is a fundamental technique in modern machine learning and information retrieval, primarily used for sampling elements from categorical distributions. It is the engine behind critical tasks such as calculating Probability Jaccard Similarity (measuring the overlap between high-dimensional vectors) and Weighted Cardinality Estimation (counting unique items with associated weights).

However, as datasets grow in dimensionality and scale, the traditional implementation of the Gumbel-Max sketch becomes a significant computational bottleneck. This paper introduces FastGM, a novel algorithm that redefines the sketching process to achieve orders-of-magnitude speedups while maintaining the exact accuracy of the original method.

The Computational Bottleneck

To generate a sketch of size $k$ for a vector with $n^+$ positive elements, the standard Gumbel-Max approach requires $O(k \times n^+)$ time. In practical applications, $k$ often reaches into the thousands, and $n^+$ can represent millions of features (e.g., in web document processing). This linear dependency on both the sketch size and the number of features makes large-scale sketching computationally prohibitive. The researchers behind FastGM sought to break this dependency, aiming for a complexity that scales more efficiently with the number of elements.

FastGM: A Queuing and Pruning Approach

The core innovation of FastGM (and its streaming variant, Stream-FastGM) is the reduction of time complexity to $O(k \ln k + n^+)$. This is achieved through two primary mechanisms:

  1. Queuing Model and Order Statistics: Rather than generating all $k$ random variables for every element simultaneously, FastGM treats each element as a "queue" that produces values. By employing exponential order statistics, the algorithm generates these variables in ascending order. This allows the system to evaluate the most promising candidates—those most likely to influence the final sketch—first.
  2. FastSearch and FastPrune:
    • FastSearch is used to rapidly populate the $k$ registers of the sketch with initial values.
  3. FastPrune establishes a dynamic threshold ($y^*$) based on the maximum value currently held in the sketch. Because variables are generated in ascending order, if an element's next smallest variable already exceeds $y^*$, that element can be safely "pruned" or ignored.

This "early stopping" logic ensures that the algorithm only performs heavy computation for elements that have a statistical chance of changing the sketch. Crucially, FastGM is an exact optimization; it produces the identical sketch as the traditional Gumbel-Max Trick, rather than an approximation.

Experimental Evaluation

The authors evaluated FastGM against synthetic data and six diverse real-world datasets, including web documents (News20, Rcv1), user ratings (Libimseti, MovieLens), and sensor network simulations.

Key Performance Metrics:

  • Synthetic Speedups: On synthetic vectors, FastGM demonstrated speedups ranging from 13x to 100x compared to $\mathcal{P}$-MinHash. Against BagMinHash, it was approximately 60x faster for vectors with 1,000 elements.
  • Real-World Efficiency: On the News20 dataset, FastGM outperformed $\mathcal{P}$-MinHash by a factor of 26x. On average, it surpassed previous state-of-the-art methods by an order of magnitude.
  • Streaming Performance: For weighted cardinality tasks in a multi-hop environment, Stream-FastGM processed data up to 52x faster than existing specialized sketches.
  • Scalability: Unlike traditional methods that slow down linearly as the sketch size ($k$) increases, FastGM’s performance remains remarkably stable, making it ideal for high-precision applications.

Insights and Future Directions

The success of FastGM stems from the realization that a Gumbel-Max sketch is essentially a competition where only the "winners" (the maximums) matter. By prioritizing high-weight elements and using order statistics to identify when a competition is effectively over, FastGM eliminates redundant calculations.

Limitations

Despite its speed, FastGM introduces a slight memory overhead. It requires storing the state of random number generators and permutation orders for each element, which may be a consideration for extremely memory-constrained environments. Additionally, the current framework is limited to non-negative vectors; adapting this logic to vectors with negative weights remains an open area for research.

Conclusion

FastGM represents a significant leap forward in sketching technology. By reframing a statistical sampling problem as a queuing and pruning task, it enables the use of Gumbel-Max sketches at a scale previously considered impractical, all while maintaining the mathematical rigor of the original trick.

Summary updated

Abstract

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 $v_{i}$ , the Gumbel-Max Trick first computes a Gumbel random variable $g_{i}$ for each positive weight element $i$ , and then samples the element $i$ with the largest value of $g_{i}+\ln v_{i}$ . 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.
BibTeX
@article{zhang2023fast,
  author = {Yuanming Zhang and Pinghui Wang and Yiyan Qi and Kuankuan Cheng and Junzhou Zhao and Guangjian Tian and Xiaohong Guan},
  title = {{Fast Gumbel-Max Sketch and its Applications}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2023},
  url = {https://openreview.net/forum?id=8DwDjwcZyu},
}
Figure