Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel analytical framework to extend the application of circulant permutations to MinHash estimators beyond the original CMinHash, enabling explicit and comparable variance expressions. By analyzing the Minner estimator, the authors demonstrate that their derived variance expressions accurately predict empirical mean square error. This work provides a generalizable method for understanding and optimizing MinHash variants that leverage circulant permutations for improved efficiency.
Circulant permutations unlock provably lower variance and storage for MinHash beyond CMinHash, with a new analytical tool that accurately predicts Minner estimator performance.
CMinHash promises a new direction for designing MinHash algorithms with reduced variance and storage space via circulant permutations. However, the original variance analysis is difficult to extend to other MinHash estimators. We present a new approach that gives explicit and easily comparable approximate variance expressions, and use it to analyze the Minner estimator. Numerical experiments show that our variance expression matches the empirical mean square error (MSE) of estimates. Our work thereby demonstrates how to apply circulant permutation to other MinHash estimators and compute their approximate variance.