Title: AHash: A Load-Balanced One Permutation Hash

Abstract: 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) Min-Hash 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 .

1. Introduction:

1.1 Background MinHash (Broder et al., 2000; Broder, 1997) is a powerful tool in processing high-dimensional data (e.g., texts) that is often viewed as a set. For a set, MinHash produces k minimum hash values, which are called MinHash values. MinHash values can support similarity computing (Broder, 1997; Chien & Immorlica, 2005; Henzinger, 2006b; Bayardo et al., 2007) , large-scale linear learning (Li & König, 2010; Li et al., 2011; 2012; Yu et al., 2012) , fast near neighbour searching (Shrivastava & Li, 2014a; Li et al., 2010; Indyk & Motwani, 1998; Shrivastava & Li, 2012) and so on. Due to the importance of MinHash, many recent works strive to improve its performance such as One Permutation Hashing (OPH) (Li et al., 2012) , Densified OPH (DOPH) (Shrivastava & Li, 2014a) , and Optimal OPH (OOPH) (Shrivastava, 2017) .

1.2. Prior Art and Their Limitations:

MinHash (Broder et al., 2000; Broder, 1997) is the most classical method but has unacceptable computation cost. Given a set S ∈ U (U is the universe of all elements), MinHash applies k random permutations (hash functions) π i : U → U , on all elements in S (see Figure 1 ). For each hash function, it computes |S| hash values but only maintains the minimum one. Then we get the k MinHash values. In practice, to achieve high accuracy, users need to compute a large number of MinHash values, i.e., k needs to be very large. Unfortunately, computing k hash functions for each element is a computational and resource bottleneck when k is large. It is showed that some large-scale learning applications need to compute more than 4000 MinHash values, which takes a non-negligible portion of the total computation time (Fernandez et al., 2019; Li, 2015) .

One Permutation Hash (OPH) (Li et al., 2012) overcomes the drawback of Min-Hash, but the produced MinHash values may be less than the demand. To overcome the drawback of MinHash, OPH reduces the number of hash computations per element from k to 1. As shown in Figure 1 , the key idea of OPH is that all elements are divided into k bins by hashing, and each bin maintains the minimum hash value respectively. Ideally, each bin will produce a MinHash value. Unfortunately, if the data is skewed or sparse, some bins could have many elements, but some bins could be empty. As a result, the number of produced MinHash values could be smaller than k. Existence of empty bins is fatal for some applications. To compute similarities, it is known that the existence of empty bins leads to the false similarity estimation (see detailed reasons in Section 2) (Shrivastava, 2017; Shrivastava & Li, 2014a; Fernandez et al., 2019) . To search near neighbours, using the empty bins as indexes leads to the false positives (see detailed reasons in Section 2) (Shrivastava & Li, 2012; 2014a) . Therefore, every empty bin needs a MinHash value, and how to appropriately fill empty bins attracts research interests in recent years (Li et al., 2012; Shrivastava, 2017; Shrivastava & Li, 2014a; b) .

Densification is helpful for filling empty bins but does not fairly use the original data. Densification, proposed by Shrivastava & Li (2014a) , is to fill the empty bins by reusing the minimum values of the non-empty bins to fix the drawback of OPH. Many densification strategies have been proposed (Li et al., 2012; Shrivastava & Li, 2014a; b; Shrivastava, 2017) . Among all densification strategies, OOPH (Shrivastava, 2017) achieves the smallest variance. It hashes IDs of empty bins to select a non-empty bin to reuse (See Figure 1 ). Although it achieves the smallest variance, it is often impossible to choose the optimal value to fill each empty bin. As shown as Figure 1 , OOPH just reuses the MinHash values of non-empty bins. Because OPH only involves three elements {A, D, C} to compute MinHash values, it places the constrains on OOPH which can only reuse these three elements. Such a reuse is unfair: the Minhash values could be reused multiple times, but other elements ({B, E}) will never be reused. Unfairness probably incurs error.

1.3. Our Solution: Amortization Hashing:

Instead of filling empty bins, this paper proposes, Amortization Hashing (AHash), which can produce fewer empty bins, so as to achieve high accuracy. As shown in Figure 1 , to minimize the unfairness of the densification, we aim to design a load-balanced hash (AHash) which produces as few empty bins as possible. After using Amortization Hashing, there could be still empty bins for very sparse sets, and we use OOPH to fill the remaining empty bins. We have proved (see Theorem 3) that the lower the number of empty bins is, the higher accuracy will be. This paper is the first attempt to design a load-balanced hash for OPH.

Intuitively, if a bin holds too many elements, it is wasted . In contrast, if a bin holds no element, it is starved . Therefore, if we can pair up a wasted bin and a starved bin, and amortize the elements between them, we can eliminate the unfairness of using densification. The details of amortization hashing are provided in Section 3. AHash is a novel solution which is orthogonal with densification, and can improve accuracy of all densification strategies. For densification strategies, filling each empty bin could incur small error. Filling more empty bins will incur larger error. To minimize the error of filling empty bins, we are expected to minimize the number of empty bins during dividing elements into bins. It is worth mentioning that AHash does not incur additional computation cost.

1.4. Key Contributions:

1) We propose a load-balanced hashing, Amortization Hashing, which can improve accuracy while retaining the same runtime efficiency. (Section 3)

2) We conduct theoretical analysis and extensive experiments, and results show that AHash can achieve higher accuracy. (Section 4)

3) We apply AHash for two data mining tasks, linear SVM, and near neighbour search, and results show AHash significantly outperforms the state-of-the-art in practical applications. (Section 4)

2. Preliminaries:

2.1 Formal Defnitions of MinHash, OPH and OOPH Formal definitions of MinHash, OPH and OOPH are as follows:

• MinHash (Broder, 1997; Broder et al., 2000) : the i th MinHash value of S is defined as:

h M inHash i (S) = 0≤i<k min{π i (S)} (1)

where π i (S) denotes the i th hashing on S. • One Permutation Hashing (Li et al., 2012) : the i th MinHash value of S is defined as:

h OP H i (S) = 0≤i<k min{π(S) ∩ Ω i } if {π(S) ∩ Ω i = ∅} Empty no element falls in this bin (2)

where π(S) denotes the hashing on S and Ω i denotes i th partition of the rang space of π(S). • One Permutation Hashing with Optimal Densification (Shrivastava, 2017) : the i th Min-Hash value of S is defined as:

h OOP H i (S) = 0≤i<k min{π(S) ∩ Ω i } if {π(S) ∩ Ω i = ∅} h OOP H j (S) no element falls in this bin (3)

where h univ (i) denotes 2-universal hashing (Shrivastava, 2017) and j = h univ (i).

2.2. Use MinHash Values for Computing Similarities:

Computing similarities is a key step for many applications like duplicate detection (Broder, 1997; Henzinger, 2006a) , semantic similarity estimation (Chien & Immorlica, 2005) , frequent pattern mining (Buehrer & Chellapilla, 2008; Chierichetti et al., 2009) and more. In the applications, the data (e.g., texts) can be viewed as 0/1 binary data (e.g., the absence/presence of a word), which is equivalent to a set. Given two sets, S 1 and S 2 , the similarity is usually measured by Jaccard Similarity, which is defined as

J(S 1 , S 2 ) = |S 1 ∩ S 2 |/|S 1 ∪ S 2 |.

For S 1 and S 2 with the same hashing, the probability of the two minimum hash values being the same is equal to Jaccard Similarity of S 1 and S 2 , which is formally shown as follow:

Pr[h(S 1 ) = h(S 2 )] = |S 1 ∩ S 2 | |S 1 ∪ S 2 | = J(S 1 , S 2 ) (4)

Such a property is called Locality Sensitive Hash (LSH) Property (Indyk & Motwani, 1998; Charikar, 2002) . Note that, if h(S 1 ) and h(S 2 ) are simultaneously empty, they are certain to collide, which violates the LSH Property. So we must handle empty bins. Given MinHash values of S 1 and S 2 , the J(S 1 , S 2 ) can be approximated as:

Ĵ(S 1 , S 2 ) = 1 k k j=1 1{h j (S 1 ) = h j (S 2 )} (5)

with 1{x} being the indicator function that takes value 1 when x is true and otherwise 0.

2.3. Use MinHash Values for Large-scale Learning:

Large-scale linear learning like training SVM (Fan et al., 2008; Hsieh et al., 2008; Joachims, 2006) is faced with extremely high-dimensional data, which emphasizes the application of hashing algorithms. Given a dataset {x i , y i } l i=1 , x i ∈ R n , y i ∈ {-1, +1}, L2-SVM solves the following unconstrained optimization problem:

min w 1 2 w T w + C l i=1 max(1 -y i w T x i , 0) 2 (6)

where C > 0 is a penalty parameter.

MinHash can be used to compact the feature vectors to reduce the feature dimensionality if the dataset is binary (i.e., each feature vector consists of only 0s and 1s) (Li et al., 2011) . Actually, each feature vector can be viewed as a set: if the i-th element of the vector is 1, then the i-th element is in the set. Thus we can use MinHash values to represent a feature vector. We use one-hot encoding (Coates & Ng, 2011; Buckman et al., 2018) for each hash value and concatenate these k values to get the new feature vector. To further reduce the dimension, Li et al. (2010) proposes that we can use only the lowest b (e.g., b=8) bits of each hash value (usually 64 bits). Thus the new feature vector is only 2 b × k-bit long, regardless of the dimensionality of the original data.

2.4. Use MinHash Values for Fast Near Neighbour Search:

Fast near neighbour search is important in many areas like databases (Broder, 1997; Friedman et al., 1975) and machine learning (Shrivastava & Li, 2012) , especially applications with high-dimensional data. Given a query set S, near neighbour search is to return other sets whose similarities with S are more than a threshold. Shrivastava & Li (2012) proposed MinHash values can be used in near neighbour search in sub-linear time complexity (i.e., without scanning the whole dataset). Specifically, a signature for a set is generated by concatenating k MinHash values like this:

EQUATION

In this way, those similar sets are more likely to have the same signature (It is not true if empty bins occur). So we can build hash tables by using the signatures as indexes and the sets as the values of the hash table entries. Moreover, to reduce the number of hash table entries, we only concatenate the lowest b bits of k hashed values to generate signatures (Li et al., 2010) . To improve the recall of the query results, we can calculate L different signatures for each set and build L hash tables, and return the union of entries from these L hash tables as the query result. For different hash tables, we should use independent hash functions to compute MinHash values. Parameters b, L, and k can be used to control the threshold of near neighbor search. Using L hash tables, the processing cost of MinHash for one query set is O(nkL) (n is the size of the query set). Shrivastava & Li (2014a) ). For a pair, the i th bin is called even bin and the (i + 1) th bin is called odd bin. For the pairs with only one empty bin, there are two cases:

• If the even bin B e is empty, we reassign B e .EvenM in with the even min of the odd bin.

• If the odd bin B o is empty, we reassign B o .OddM in with the odd min of the even bin.

For the pairs with two simultaneously non-empty or empty bins, we keep them unchanged.

After the amortization, we collect k MinHash values from k bins and there are two cases (See Figure 2 ):

• For each even bin with both even and odd mins, we delete the odd min.

• For each odd bin with both even and odd mins, we delete the even min.

If there are still empty bins, we conduct densifying like OOPH, which rarely happens because AHash significantly reduces the empty bins. Formally, for even bins,

h AHash i (S) =        min{π e (S) ∩ Ω i } π e (S) ∩ Ω i = ∅ min{π o (S) ∩ Ω i } π e (S) ∩ Ω i = ∅ and π o (S) ∩ Ω i = ∅ min{π e (S)

∩ Ω j } i th bin is empty and π e (S) ∩ Ω j = ∅ Empty others (8)

EQUATION

where π e (S) (π o (S)) denotes the even (odd) hash values of S and Ω i denotes i-th partition of the range space of π(S). The formula for odd bins is similar.

3.2. Time and Memory Overhead:

For time overhead, AHash keeps comparable runtime efficiency with OPH, the fastest variant of MinHash. Although each bin maintains one more hash values than OPH, the additional runtime cost is negligible because of the memory access locality of the insertion (two values in a bin). Note that AHash has much less empty bins which require densification compared with OOPH, which can save the time cost.

For memory overhead, AHash also provides k MinHash values, which is the same as MinHash and OOPH. During the Insertion, the cost of storing two hash values in a bin is acceptable.

For the common setting (hundreds of bins and 64-bit MinHash values), the vector of bins with two values per bin can be totally fitted into L1 cache (usually larger than 32 KB), the fastest memory.

4. Experiments and Applications:



4.1. Setup:

We use three publicly available datasets2 : a) RCV1: The dataset is a collection for text categorization. It has 20, 242 sets and the size of the set is on average 73. The dimensionality (range space) of elements is 47, 236. b) NEWS20: The dataset is a collection of newsgroup documents. It has 19, 996 sets and the size of the set is on average 402. The dimensionality (range space) of elements is 1, 355, 191. c) URL: The dataset is a collection for identifying suspicious URLs. It has 100, 000 sets and the size of the set is on average 115. The dimensionality (range space) of elements is 3, 231, 961.

We use two metrics to measure the performance: a) Mean Square Error (MSE) is defined as E[( Ĵ -J) 2 ]. We use MSE to measure the accuracy of computing the Jaccard Similarity. b) F1-score is defined as 2P •R (P +R) , where P is the precision rate and R is the recall rate. We use F 1 -score to evaluate the performance of fast near neighbour search.

We implemented all algorithms in C++ which are publicly available3 on GitHub. All experiments are conducted on laptop with 2.9 GHZ Intel Core i7 CPU. To measure the accuracy of AHash, we generate 6 pairs of sets from the data RCV1, with varying similarities. Because it is difficult to use original sets to form the pairs with high similarity, we unite some original sets as a new set to form the pairs. Detailed statistics is shown in Table 1 .

4.2. Accuracy and Speed:

Figure 3 presents the results about the accuracy of computing similarities with varying k (the number of Minhash values). Regardless of the similarity level, AHash is more accurate than OOPH and MinHash (e.g., at k = 512, the MSE of AHash is lower than OOPH by 13.2%-31.7%). For Figure 3 , the absolute values of MSE are too small, so it's a little hard to see the difference in the values. But the improvements are significant (up to 29.021%), e.g., the MSE of AHash is 29% lower than OOPH with k = 512 in Figure 3(b) .Note that the gain of AHash is more significant when the number of bins is appropriate (not extremely small or large). The reason is that if k is extremely small, all bins are non-empty. Therefore, AHash has no need for amortization. To the other extreme, if k is extremely large, only a small portion of bins are non-empty and the amortization plays a limited role. Fortunately, with a practical and commonly used configuration, AHash presents significant gains.

Table 2 shows that the speed of computing k MinHash values of AHash is comparable with OOPH, which is two orders of magnitude faster than MinHash. AHash does not hurt the runtime efficiency of OOPH. AHash and OOPH both use much less runtime to more accurately compute the similarity.

Under review as a conference paper at ICLR 2020 4.3 Linear Learning 10 -3 10 -2 10 -1 10 0 10 1 10 2 99.8 99.9 10 -3 10 -2 10 -1 10 0 10 1 10 2 10 -3 10 -2 10 -1 10 0 10 1 10 2 96.9 99.8 99.9 Accuracy(%) We use LIBLINEAR (Fan et al., 2008) to train a L 2 -nomarlized SVM to measure the effectiveness of AHash in reducing the dimensionality of the training data. We experimented with varing penalty parameter C, which follows other works (Li et al., 2011; Yu et al., 2012) . In this way, it is more easy to reproduce our experiments.

C MinHash OOPH AHash (c) NEWS20

Figure 4 shows that AHash can achieve 99% test accuracies and outperforms OOPH. Compared with training with the original high-dimensional data, the training based on the new feature vectors built by AHash is usually two orders of magnitude faster. Figure 4 shows AHash can further reduce the error, e.g., the error of AHash on average is 46.81% lower than OOPH in Figure 4 (b). AHash can achieve the satisfied accuracy, close to 100%. We apply AHash with the optimization of b-bit hashing (Li et al., 2010) for fast near neighbour search. Given a query set, threshold of the similarity is 0.5, that is, near neighbour search should return sets whose similarity with the query set is more than 0.5. It is important to balance the precision and recall to measure the effectiveness on near neighbour search. Therefore, we use F 1 -score as the metric.

4.4. Near Neighbour Search:

Figure 5 shows that the F 1 -score of AHash is significantly higher than MinHash and OOPH on all three datasets. Note that the trend of F 1 -score with varying L is not monotonous. With L increasing, the number of reported elements and the number of reported near neighbours both increases, but their growth trends are of randomness. In spite of this, AHash can outperform OOPH and MinHash under most of parameter settings.

5. Conclusion:

We propose Amortization Hashing which can improve the accuracy of One Permutation Hashing and densification strategies without loss in runtime efficiency. AHash outperforms the state-of-the-art OOPH in similarity estimating, large-scale learning and fast near neighbour searching.

A Theoretical Analysis:

Theorem 1 Unbiased Estimator

EQUATION

E( ĴAHash ) = J (11)

where ĴAHash denotes the estimator given by AHash. Theorem 1 is to show the estimator of AHash is following the LSH property and unbiased.

Proof A.1 For convenience, we define some Boolean values:

Iemp,i = 0≤i<k

1 For both i th bins of S1 and S2, no elements falls in them 0 otherwise (12)

Imat,i = 0≤i<k

1 Before Amortization, the values of the i th bins of S1 and S2 are the same 0 otherwise (13)

EQUATION

Obviously, for simultaneously non-empty bins, AHash is following the LSH property:

EQUATION

Next, we prove that the Amortization for simultaneously empty bins is unbiased:

Iemp,i = 1 and I A emp,i = 0 -→ Iemp,j = 1 (j = i 2 + (i + 1)%2) E(I A mat,i |Iemp,i = 1 and I A emp,i = 0) = E(Imat,j|Iemp,j = 1) = J (17) If I A emp,i = 1, i.e.

, there is still the pair of bins which are simultaneously empty after Amortization, we use unbiased Optimal Densification (Shrivastava, 2017) to fill such bins.

Theorem 2 Reducing Empty Bins

EQUATION

where Nemp = k i=1 I i emp is the number of simultaneously empty bins.

Proof A.2 (Li et al., 2012) proves the expectation of the number of simultaneously empty bins of OPH is:

EQUATION

)

where f is |S1 ∪ S2| and D is the dimensionality of the universal hashing function used. The process of OPH can be viewed as randomly throwing f balls into k bins. For AHash, because k bins are paired up, the process of AHash can be viewed as randomly throwing f balls into k 2 bins. Obviously, Nemp of AHash is smaller than OPH:

EQUATION

Proof A.3 We define two Boolean values with 1{x} being the indicator function that takes 1 when x is true and otherwise 0.

M A j = 1{I A emp,j = 0 and h AHash j (S1) = h AHash j (S2)} ( 22)

EQUATION

The estimator given by AHash and the variance of AHash can be rewritten as follows using these two values.

EQUATION

V ar( ĴAHash ) = E((

EQUATION

Theorem 1 proves (E( ĴAHash )) 2 = J 2 . Define two notations:

EQUATION

OOPH uses conditional expectation to simplify variance analysis. To conveniently compare with OOPH, we follow its method where E(.|m) means E(.|k

EQUATION

Because M A i and M E i are Boolean values,

E[ k i=1 ((M A i ) 2 + (M E i ) 2 )|m] = E[ k i=1 (M A i + M E i )|m] = k × J (28)

To analyze another three terms, we provide four probability equations for bins before the amortization.

P r(Iemp,j = 1) = Pe = ( k -1 k ) |S 1 ∪S 2 | (29) P r(Iemp,j = 0) = P f = 1 -Pe (30)

Pr(Iemp,j=0 and the mins from two j-th bins have one and only one position)

EQUATION

Pr(Iemp,j=0 and the mins from two j-th bins have two positions (odd/even))

= P d = P f -Ps (32)

Define one notation:

Ĵ = |S1 ∩ S2| -1 |S1 ∪ S2| -1 (33)

The values of following three terms is proved by classifying different combinations of bins and applying probability equations and the property of indicator functions.

E(:

i =j

EQUATION

Hence, we get that

EQUATION

)

For OOPH, the variance is

EQUATION

M N j = 1{Iemp,j = 0 and h OP H Because AHash reduces Nemp, AHash using Optimal Densification (Shrivastava, 2017) can achieve lower variance compared with OOPH.

:

https://github.com/AHashCodes/AHash

https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/binary.html

https://github.com/AHashCodes/AHash

Figures and Tables:

Figure 1: A toy example of existing works and our design goal with k = 5. The hash values of elements at the bottom are MinHash values.

Figure 2: A toy example of AHash with k = 5.

Figure 3: Average MSE in Jaccard Similarity estimation with varing the number of MinHash values (k). Results are averaged over 2000 repetitions.

Figure 4: SVM test accuracy. We set k as 150 and apply the b-bit hash with b as 8.

Figure 5: F 1 -score of fast near neighbour search. We set k as 10 and apply the b-bit hash with b as 32. Results are averaged over 2000 queries.

k + m 2 m 2 (J Ĵ -J) ≤ 0 and m ≥ m =⇒ h(m) ≤ h(m ) =⇒ V ar( ĴAHash ) ≤ V ar( ĴOOP H )(41)

Pairs of SetsPairs JS |S 1 | |S 2 |

Table content: <table><tr><td/><td/><td/><td/><td colspan="3">Table 2: Time (Second) to compute 256 MinHash val-</td></tr><tr><td/><td colspan="2">A</td><td>0.27 750 567</td><td>ues</td><td/></tr><tr><td/><td colspan="2">B</td><td>0.34 750 748</td><td>Hash</td><td colspan="2">RCV1 NEWS20 URL</td></tr><tr><td/><td colspan="2">C</td><td>0.44 750 870</td><td>MinHash</td><td>3.44</td><td>20.45</td><td>25.83</td></tr><tr><td/><td colspan="2">D</td><td>0.53 750 751</td><td>OOPH</td><td>0.024</td><td>0.13</td><td>0.18</td></tr><tr><td/><td colspan="2">E</td><td>0.61 750 892</td><td>AHash</td><td>0.025</td><td>0.14</td><td>0.18</td></tr><tr><td/><td colspan="2">F</td><td>0.71 750 719</td><td/><td/></tr><tr><td/><td>0.0030</td><td/><td/><td/><td/></tr><tr><td/><td>0.0025</td><td/><td>MinHash OOPH</td><td/><td/></tr><tr><td>MSE</td><td>0.0015 0.0020</td><td/><td>AHash</td><td/><td/></tr><tr><td/><td>0.0010</td><td/><td/><td/><td/></tr><tr><td/><td>0.0005</td><td/><td/><td/><td/></tr><tr><td/><td>0.0000</td><td colspan="2">128 256 512 1024 2048 k</td><td/><td/></tr></table>

Peer review (iclr2020):
*** 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.