Minwise Hashing (MinHash) is a fundamental method to compute set similarities and compact high-dimensional data for efficient learning and searching. The bottleneck of MinHash is computing k (usually hundreds) MinHash values. One Permutation Hashing (OPH) only requires one permutation (hash function) to get k MinHash values by dividing elements into k bins. One drawback of OPH is that the load of the bins (the number of elements in a bin) could be unbalanced, which leads to the existence of empty bins and false similarity computation. Several strategies for densification, that is, filling empty bins, have been proposed. However, the densification is just a remedial strategy and cannot eliminate the error incurred by the unbalanced load. Unlike the densification to fill the empty bins after they undesirably occur, our design goal is to balance the load so as to reduce the empty bins in advance. In this paper, we propose a load-balanced hashing, Amortization Hashing (AHash), which can generate as few empty bins as possible. Therefore, AHash is more load-balanced and accurate without hurting runtime efficiency compared with OPH and densification strategies. Our experiments on real datasets validate the claim. All source codes and datasets have been released on GitHub anonymously 1 .
*** Summary ***
MinHash is a well-known method for approximating set similarities in terms of the jaccard similarity. The idea is to use k random permutations (hashes) on all elements of the sets and check how often two sets hash into the same bucket. Larger values of k yield more accurate estimates of the set similarities but require more time to compute. One permutation hashing (OPH) aims to reduce the number of hash computations per element to 1 and maintaining bins. However, some of those bins may remain empty which negatively influences the similarity estimate. Optimal OPH (OOPH) hashes empty bins to non-empty bins and effectively reuses bins. This paper proposes Amortization Hashing (AHash) which reduces the occurrence of empty bins and thus leads to better similarity estimates.
*** Evaluation ***
The paper proposes an interesting idea for approximating set similarities much faster than MinHash. However, I have some issues with the submission.
I believe that the manuscript has a limited impact. The approach performs on par or marginally better as OOPH within the first and only reasonable experiment (4.2). As the authors state themselves on the page break 9/10, the advantage of AHash vanishes for small and large values of k. Hence, AHash only benefits of moderate choices of k. Moreover, I can see that OOPH might have a minor problem of estimating the set similarities which AHash aims to fix, but why should it outperform MinHash in terms of accuracy? Why are the pairs of set only chosen from RCV1? Why those particular set sizes? Why does no plot show standard deviation/error?
The remaining experiments yield very limited insight. Considering a linear SVM on standard datasets where the test error is >99.8% seems to be obsolete. In addition, the most important parameter k is held fix to an arbitrary value. Same holds for b. Since AHash only benefits from moderate sizes of k, why was k chosen in favor of AHash? The performance should definitely be shown in dependence of k. Instead, the most unimportant parameter (C) is varied. This should have been done in a proper cross-validation. Similar arguments hold for the near neighborhood search. What is the query set being used?
There are more flaws within the manuscript. The mathematical presentation is rather poor. The theorems lack text and assumptions and solely consist of equations. The corresponding proofs are also short on text and hard to follow. Unfortunately, there is no analysis of the expected error as a function of k. The proof of Theorem 3 is almost two pages and should be moved to the supplementary material since it does not provide much insight; it just distracts the reading flow. In addition, every equation is numbered but none is ever referenced. The citation style (numbers in round brackets) is really uncommon and can be easily confused with equation numbers. Most importantly, I want to note that a different font was used and that the spacing was clearly tricked in several places (e.g. within Section 4). This makes it especially hard to judge whether the manuscript has the correct length.
*** Further Comments ***
- The font was changed. It does not match the font of the other submissions.
- The spacing is tricked in several places, especially in Section 4.
- Links [1,29] should not be references but footnotes.
- Citations should never be in round brackets like (1), because they can be confused with equation numbers. Instead they should be in square brackets like [1] or, more preferably, the natbib package should be used as in the ICLR style guidelines.
- What does OOPH stand for? It is never stated.
- Every equation has a number, but none is ever referenced.
- Math/Equations are part of the text and should be treated as such, i.e., there should be proper punctuation marks.
- What is a 2-universal hashing?
- Algorithm 1: "output range" sounds like an interval whereas the number of distinct hash values is meant.
- "(14) proposed", no past tense
- Instead of "(11) proposes", please use "Shrivastava and Li [11] propose"
- Why "Theorem 1" and "Proof 3.1"?
- Why are the theorems lacking the assumptions and text? They basically consist of equations.
- Theorem 3 should have a "less or equal" instead of a "strictly less".
- Eq. (40): "0andm"
- Why does Proof 3.3 have a end of proof sign (not right-aligned) but the other proofs don't?
- None of the experimental results shows standard deviations/errors although the experiments are repeated several times. Why? It would be also nice to see whether the approximation tends to over- or underestimate J. This could be done with a violin plot.
- How are the pairs of sets in Section 4.2 chosen and why only from RCV1? This seems to be the most important experiment.
- Why is k (and b) fixed to an arbitrary value in the remaining experiments? Please select C within a proper cross-validation.
- There are a lot of enumerations which unnecessarily make the manuscript longer, e.g. in Sections 1.4, 2.1 and 4.1. In addition, the proof of Theorem 3 almost takes two pages but is not super informative. It should be moved to the supplementary material. This in combination with the font mismatch makes it difficult to determine the real length of the submission.
- It is nice that the source code is published online, but uncommented c++ code is not really helpful.