Extending CMinHash with Circulant Permutations: A New Variance Analysis Framework

Introduction: The Evolution of MinHash and the Promise of CMinHash

In an era of exploding data, quickly estimating the similarity between two sets (Jaccard similarity) has become a core problem in tasks such as recommendation systems, deduplication, and clustering. The MinHash algorithm and its variants have long been a powerful tool for solving this problem. In recent years, a new method called CMinHash has been proposed, which designs MinHash algorithms through Circulant Permutation, promising to reduce variance while also reducing storage space. This has opened up new directions for the MinHash family.

However, the variance analysis of the original CMinHash is quite complex and difficult to directly extend to other MinHash estimators. A recent paper proposes a new analytical framework that provides an explicit and easily comparable approximate variance expression, validated using the Minner estimator as an example. Numerical experiments show that this expression closely matches the empirical mean squared error (MSE). This research paves the way for applying circulant permutations to a broader range of MinHash estimators.

Background: MinHash and Circulant Permutations

The core idea of MinHash is to use random hash functions to map set elements to minimum hash values, and to estimate Jaccard similarity by comparing multiple hash values. Traditional MinHash requires multiple independent hash functions, resulting in high storage and computation costs. The innovation of CMinHash lies in using circulant permutations—a permutation method based on circulant matrices—which requires only a single random seed to generate multiple correlated but approximately independent hash functions, thereby significantly reducing storage while maintaining accuracy.

The mathematical properties of circulant permutations give the hash functions controllable correlations, which is the key to reducing variance. However, the variance analysis in the original paper relies on specific assumptions and is difficult to generalize to other estimators (such as Minner). This limits the generality of the circulant permutation method.

Jaccard similarity is a fundamental metric for measuring the degree of similarity between two sets, defined as the ratio of the intersection size to the union size of the two sets, with values ranging from 0 to 1. In recommendation systems, it can be used to measure the overlap of user interest sets; in web deduplication, it can be used to determine the degree of word set overlap between two documents. Directly computing exact Jaccard similarity requires traversing the entire set, which is prohibitively expensive in large-scale data scenarios, so the industry generally uses probabilistic algorithms like MinHash for approximate estimation. The theoretical basis of MinHash is that if a random permutation is applied to set elements, the probability that the minimum hash values of two sets are equal is exactly equal to their Jaccard similarity. Based on this property, unbiased estimates can be obtained through multiple independent permutations. Understanding the definition of Jaccard similarity and the unbiasedness principle of MinHash is a prerequisite for grasping the motivation behind CMinHash improvements.

Mean squared error (MSE) is a commonly used metric for evaluating estimator accuracy, defined as the expected value of the squared difference between the estimated value and the true value, which can be decomposed into the sum of the squared bias and the variance. In MinHash-type algorithms, estimators are typically unbiased, so MSE is mainly determined by variance. Reducing variance means obtaining more stable estimation results under the same number of hash functions or storage budget. The core goal of improved methods like CMinHash and Minner is precisely to compress variance by designing the correlation structure between hash functions. In numerical experiments, the authors verify the accuracy of the new framework by comparing theoretical approximate variance with empirically simulated MSE, so understanding the composition of MSE helps in interpreting their experimental design and conclusions.

New Method: Explicit Approximate Variance Expression

To address the above issues, researchers proposed a new analytical approach. Instead of directly deriving the exact variance, they constructed an explicit and easily comparable approximate variance expression. This expression is based on the spectral properties of circulant permutations and can quickly compute the variance of different estimators under given parameters.

Specifically, the new method decomposes the variance of the estimator into a part related to circulant permutations and a part related to the data distribution, making variance comparisons between different estimators intuitive. The authors use the Minner estimator as an example to demonstrate how to apply this framework to compute its approximate variance. Minner is an improved MinHash estimator that further reduces variance by combining multiple minimum hash values.

The spectral properties of circulant matrices and circulant permutations are the key mathematical background for understanding the new variance analysis framework. A circulant matrix is a special type of matrix where each row is obtained by cyclically shifting the previous row one position to the right. All its eigenvectors can be given by the discrete Fourier transform, and its eigenvalues correspond to the Fourier transform coefficients of the first row of the matrix. Because of this structure, multiplication of circulant matrices can be performed in O(n log n) time using the fast Fourier transform, and their eigenvalues have analytical expressions. When CMinHash uses circulant matrices to generate multiple correlated hash functions, the covariance structure between hash functions is entirely determined by these eigenvalues. The new method leverages this spectral decomposition to write the estimator variance as an explicit function of the eigenvalues, thereby bypassing the complex derivation in the original CMinHash that relies on specific assumptions. Mastering the spectral properties of circulant matrices helps in understanding why the new expression can be "explicit and easily comparable."

The Minner estimator is an improved scheme in the MinHash family that further reduces variance by combining multiple minimum hash values. Its basic idea is: instead of using only a single minimum value, it takes several smallest hash values for each set, and then performs some weighted or ordered combination of these values to estimate Jaccard similarity. Compared to standard MinHash, Minner typically has lower variance under the same hash budget, but its variance analysis is also more complex. The authors chose Minner as a case study precisely to demonstrate that the new framework can cover not only CMinHash itself but also handle such structurally more complex estimators, thereby proving its generality. Understanding Minner's combination idea helps in grasping the value of the new variance expression in terms of extensibility.

Experimental Validation: Approximate Variance Matches Empirical MSE

To verify the accuracy of the new expression, the authors conducted a series of numerical experiments. They compared the theoretical approximate variance with the empirical mean squared error (MSE) obtained through extensive simulations. The experiments covered different set sizes, Jaccard similarities, and circulant permutation parameters.

The results show that the approximate variance is highly consistent with the empirical MSE, with extremely small errors especially when the set size is large. This proves the effectiveness of the new method and also indicates that circulant permutations can be safely applied to other estimators such as Minner. In addition, the experiments revealed the influence patterns of circulant permutation parameters on estimation accuracy, providing guidance for parameter selection in practical applications.

Significance and Outlook: Advancing MinHash Algorithm Design

The contribution of this work lies not only in extending CMinHash but also in providing a general variance analysis tool. In the future, researchers can use this framework to quickly evaluate newly proposed MinHash estimators and accelerate algorithm iteration. At the same time, the introduction of circulant permutations makes MinHash more attractive in storage-constrained scenarios (such as embedded devices and large-scale distributed systems).

Interestingly, the method is still based on approximate analysis and may not be sufficiently accurate for certain extreme data distributions. But overall, it builds a bridge between theoretical analysis and practical deployment of MinHash algorithms. As data scales continue to grow, such efficient similarity estimation techniques will become increasingly important.

Conclusion

The combination of circulant permutations and MinHash is driving similarity estimation technology toward greater efficiency and generality. The newly proposed variance analysis framework makes CMinHash no longer isolated but rather an extensible methodology. For developers working in big data deduplication, recommendation systems, or information retrieval, paying attention to this direction may bring new optimization ideas.