# C-OPH: Improving the Accuracy of One Permutation Hashing (OPH) with Circulant Permutations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 18 Nov 2021.

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

- [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)
- [Parallel Index-Based Structural Graph Clustering and Its Approximation](https://mlsanity.com/paper/2012.11188/) (2020)
- [C-MinHash: Rigorously Reducing K Permutations to Two](https://mlsanity.com/paper/2109.03337/) (2021)
- [C-MinHash: Practically Reducing Two Permutations to Just One](https://mlsanity.com/paper/2109.04595/) (2021)

## Built on by (most cited first, 2 of 2)

- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)
- [Understanding Circulant Permutation to Extend the CMinHash Estimator](https://mlsanity.com/paper/2610.18551/) (2026)

## Abstract (arXiv)

Minwise hashing (MinHash) is a classical method for efficiently estimating the Jaccrad similarity in massive binary (0/1) data. To generate K hash values for each data vector, the standard theory of MinHash requires K independent permutations. Interestingly, the recent work on "circulant MinHash" (C-MinHash) has shown that merely two permutations are needed. The first permutation breaks the structure of the data and the second permutation is re-used K time in a circulant manner. Surprisingly, the estimation accuracy of C-MinHash is proved to be strictly smaller than that of the original MinHash. The more recent work further demonstrates that practically only one permutation is needed. Note that C-MinHash is different from the well-known work on "One Permutation Hashing (OPH)" published in NIPS'12. OPH and its variants using different "densification" schemes are popular alternatives to the standard MinHash. The densification step is necessary in order to deal with empty bins which exist in One Permutation Hashing. In this paper, we propose to incorporate the essential ideas of C-MinHash to improve the accuracy of One Permutation Hashing. Basically, we develop a new densification method for OPH, which achieves the smallest estimation variance compared to all existing densification schemes for OPH. Our proposed method is named C-OPH (Circulant OPH). After the initial permutation (which breaks the existing structure of the data), C-OPH only needs a "shorter" permutation of length D/K (instead of D), where D is the original data dimension and K is the total number of bins in OPH. This short permutation is re-used in K bins in a circulant shifting manner. It can be shown that the estimation variance of the Jaccard similarity is strictly smaller than that of the existing (densified) OPH methods.