Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Min-wise hashing (MinHash) is a fundamental and popular algorithm in machine learning. This paper proposes Circulant MinHash (C-MinHash) to approximate the Jaccard similarity in massive binary data. Compared with MinHash, C-MinHash only requires two (or maybe one in practice) random permutations in a circulant manner for approximation. The authors also systematically demonstrate that the C-MinHash can provide a smaller estimation variance than MinHash. Extensive experiments validate the effectiveness of C-MinHash. 


main_review: Pros:
1. I like the idea of using circulation and shifting for the hashing strings, which can reduce the number of permutations but still introduce randomness (even though not entirely independent).

2. The authors systematically show that C-MinHash-($\sigma$,$\pi$) has uniformly lower Jaccard estimation variance than the vanilla MinHash.

3. The one permutation variant C-MinHash-($\pi$,$\pi$) is practically interesting, which can use a single permutation to achieve very similar results as C-MinHash-($\sigma$,$\pi$).

4. Extensive experiments justify their theoretical analysis over MinHash.

Cons:
1. As claimed in the conclusion section, there exist other works improving MinHash with much fewer permutations, such as [1,2,4,6]. Thus, it will be more convincing to show more baselines in the numerical experiments in Section 4 rather than using MinHash only. 

2. Many important related works about MinHash are missing, such as [1-6]. I suggest the authors discuss more related works and illustrate their difference to C-MinHash.

Reference:

[1] Li, Ping, Art Owen, and Cun-hui Zhang. "One Permutation Hashing." Advances in Neural Information Processing Systems 25 (2012): 3113-3121.

[2] Shrivastava, Anshumali, and Ping Li. "Densifying one permutation hashing via rotation for fast near neighbor search." In International Conference on Machine Learning, pp. 557-565. PMLR, 2014.

[3] Shrivastava, Anshumali, and Ping Li. "Improved densification of one permutation hashing." In Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, pp. 732-741. 2014.
 
[4] Shrivastava, Anshumali. "Optimal densification for fast and accurate minwise hashing." In International Conference on Machine Learning, pp. 3154-3163. PMLR, 2017.

[5] Li, Ping, Xiaoyun Li, and Cun Hui Zhang. "Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling." Advances in Neural Information Processing Systems 32 (2019).

[6] Jia, Peng, Pinghui Wang, Junzhou Zhao, Shuo Zhang, Yiyan Qi, Min Hu, Chao Deng, and Xiaohong Guan. "Bidirectionally Densifying LSH Sketches with Empty Bins." In Proceedings of the 2021 International Conference on Management of Data, pp. 830-842. 2021.
summary_of_the_review: Overall, the idea of this paper looks very promising, and the authors also achieve better theoretical results in terms of lower Jaccard estimation variance. However, the experiments and the related work are a lit weak. Such limitations justify my initial rating.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes C-MINHASH to improve vanilla MINHASH. Instead of using K random permutations to generate K hash values, C-MINHASH requires only two permutations. Theoretically, C-MINHASH provides unbiased estimate, and its variance is smaller than MINHASH. Extensive empirical experiments verify the theoretical analysis. 
main_review: The fact that using two permutations provides smaller than vanilla MINHASH is interesting, and the theoretical analysis of the paper is extensive. I think the paper can improve in the following perspective. 
1. There are some works on improving MINHASH, such as one permutation hashing and densifying one permutation hashing. The relation between MINHASH and these works needs to be thoroughly discussed. Instead, the paper only says C-MINHASH can be used to improve one permutation hashing. Moreover, experiments should also be conducted to compare with these works.
2. The benefits of using only two permutation is not well justified. Existing works (one permutation hashing and densifying one permutation hashing) only need to conduct permutation once while MINHASH still needs to conduct permutation K times. The storage cost may not be a concern as one can generate random permutations on the fly without storing them.
I will raise my score if the concerns are addressed.    

summary_of_the_review: The method and theoretical analysis are interesting. However, the paper lacks a clear justification of the benefits of C-MINHASH and a through comparison with related works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an effective approach for MinHash by permutating data vectors. It first randomly shuffles the data to break structures exhibited in the original data and then performs permutation K-times to obtain K hash values. Besides, this paper proposes an approach that performs only one permutation to compute hash values. This paper shows the theoretical approximation error of the proposed approach. By using text and image datasets, it shows that experimental results follow the results of the theoretical analysis.
main_review: Basically, I like the paper's motivation; it is quite a fundamental research problem to approximate the Jaccard similarity for large-scale data efficiently. Besides, this paper is well structured, and the theoretical background of the proposed approach is well described in the paper. Specifically, I really appreciate that this paper conducted an excellent job revealing the proposed approach's theoretical approximation quality. Furthermore, it experimentally confirms that the experimental results follow the theoretical results. 

However, I am concerned about the experiment since the paper compares the proposed approach to only the original approach of MinHash. Since MinHash is a popular approach with a long history, many variant approaches have been proposed below. Therefore, it needs to compare the proposed approach to the previous approach to demonstrate its usefulness.

- Li et al., b-Bit Minwise Hashing for Estimating Three-Way Similarities
- Ioffe, Improved Consistent Sampling, Weighted Minhash and L1 Sketching
- Manasse et al., Consistent weighted sampling
- Shrivastava, Exact Weighted Minwise Hashing in Constant Time
summary_of_the_review: This paper is well-written.
It needs to compare the proposed approach to the previous approaches.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper designs an improved version of the classical MinHash data structure for calculating the Jaccard similarity between two binary strings.

The classical MinHash data structure generates K hash values for a binary string by generating K independent random permutations of the binary string and taking the index of the first “1” in the permuted string as the hash value in each random permutation. The estimator is then the percentage of equal hash values out of K hash values for the two binary strings. This is an unbiased estimator.

This paper’s algorithm, called C-MinHash, first applies a random permutation to the binary string. For the K hash values, instead of using K independent random permutations, the new algorithm uses the same permutation but shifted by 1, 2, …, K positions. The estimator is the same as that of the MinHash and can be easily shown to be unbiased. The paper then shows that this simple scheme, with only two independent random permutations, yields a smaller variance than that of MinHash.

main_review: This is an interesting and surprising result as the algorithm is neat and simple, and improves on a classical algorithm. The proof seems straightforward with laborious calculations, which I did not check carefully. Hence, intuition as to why it works is important. Unfortunately, the paper does not provide the intuition at all and I hope the authors can elaborate on this.

From an algorithmic perspective, since the variance depends on the Jaccard similarity itself, one can only assume the worst case that the variance is 1/(4K) and pick K accordingly to obtain an (1+/-eps)-approximation. The new variance in Theorem 3.1 has an almost intractable non-closed expression for the variance. How does one choose K now? Is there a neater (though weaker) upper bound for the variance in Theorem 3.1?

summary_of_the_review: Personally I like the paper and I hope that the paper will be accepted. ~However, I strongly feel that this paper should probably be merged with a separate paper by the same authors on reducing two permutations to one to tell a full story. I had a look at the arXiv version (https://arxiv.org/pdf/2109.04595.pdf) of the other paper and the main proof is just 4 pages. There is no compelling reason to split them into two papers. ~
review_title: null

Meta-review: This was a somewhat unusual submission in that the authors tried to motivate their paper by pointing to a separate anonymous manuscript.  However, the authors didn't seem to want to confirm they would merge the manuscripts when asked about this. It was thought that in fairness the submitted manuscript should be judged on its own. After discussion, it was agreed that the submitted paper on its own, did not generate enough enthusiasm to merit acceptance.
Decision: Reject