AHash: A Load-Balanced One Permutation Hash
Authors: Chenxingyu Zhao
Jie Gui
Yixiao Guo
Jie Jiang
Tong Yang
Bin Cui
Gong Zhang
Venue:  (2020)
Keywords: Data Representation
Probabilistic Algorithms

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) 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 provided as Supplementary Materials and released on GitHub anonymously.

Under review as a conference paper at ICLR 2020
AHASH: HASH
A LOAD-BALANCED ONE PERMUTATION
A Anonymous authors
Paper under double-blind review
A ABSTRACT
Minwise Hashing (MinHash) is fundamental method to compute set simi- larities and compact high-dimensional data for efficient. learning and search- ing. The bottleneck of MinHash is computing k (usually hundreds) Min- Hash values. One Permutation Hashing (OPH) only requires one permuta- tion (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 ele- ments in bin) could be unbalanced, which lcads to the existence of empty bins and false similarity computation Several strategies for densification, that is, filling emply bins, have been proposed. However, the densification is just a remedial stralegy and cannol. 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 advance. In this paper, we propose load-balanced hash- ing, Amortization Hashing (AHosh), which can generate as few empty bins as possible. Therefore, AHash is more load- bad-balanced and accurate without hurting runtime efficiency compared with OPH and densification strategies. Our experiments on real datascts validate the claim. All source codes and datasets have been released GitHub anonymously
INTRODUCTION
1.1 BACKGROUND
MinHash (Broder et al. 2000 Broder 1997 is powerful tool in processing high-dimensional data (e.g., texts) that is often viewed as a set. For a set, MinHash produces & minimum hash values, which are called MinHass values. MinHlash values can support similarity
computing (Broder 1997 Chien & Iumorlica, 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, (012) and 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 set V (? is the universe of all elements), MinHash applics l random permutations (hash functions) π. W + W, on all clements in S (see Figure D. For cach hash function, computes |S] hash values but only maintains the minitum one. Then we get the & MinHlash values. In practice, to achieve high accuracy, users need to compute a large number of MinHash values, i.e., needs to be very large. Unfortunately, computing l hash functions for each element is computational and resource bottleneck when is large. It is showed that some large-scale learning applications need to
"htrps//ggttmbb.co/// waw.aooooomaaaahaaaaCea AHash

---

Under review as a conference paper at ICLR 2020
compute more than 4000 MinHash values, which takes a non-negligible portion of the total
computation time [Fennandez 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 & to 1. As shown in Figure I the key idea of OPH is that all elements are divided into & bins by hashing, and each bin maintains the minimum hash value respec- lively. Ideally, each bin will produce a MinHlah 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.
A
Set B
E
D
D
8
E
8
8
8
E
B
A
C
A
D
C
A
B D
E
C
B
A
C
A
A
C
A
D
E
C
MinHash
OPH
Design Goal
ООPH
Figure 1: A toy example of existing works and our design goal with h == 5. The hash values of elements at the bottom are MinHash values.
Existence of empty bins is fatal for some applications. To compute similarities, it is known that the existence of emply 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 emply bins by
reusing the minimum values of the non-emply bins to fix the drawback of OPH. Many
densification strategies have been proposed (Li et al. 2012 Shrivastava
Li 2014a b
Shrivastaval 2017]. Among all densification strategies, OOPH (Shiivstaaaa 2017 achieves the smallest variance. It hashes IDs of empty bins to select a non-empty bin to reuse (Sec Figure D. Although it achieves the smallest variance, it is often impossible to choose the optimal value to fill cach empty bin. As shown as Figure [ 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 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 Figure] [ to minimize the unfairness of the densification,
aim to design boad-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 load-balanced hash for OPH.
2

---

Under review as a conference paper at ICLR 2020
Intuitively, if bin holds too many elements, it is wasted. In contrast, if bin holds no element, is starved. Therefore, we can pair up a wasted bin and a starved bin, and amortize the elements between them, The details of amortization hashing are provided in Section 3
eliminate the unfairness of using densification.
AHash is novel solution which is orthogonal with densification, and improve accuracy of all densification strategics. For densification strategics, filling cach 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 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
3) We apply AHash for two data mining tasks, linear SVM, and near neighbour search, and results show AHHash significantly outperforms the saate-of-the-ane in practical applications. (Section
PRELIMINARIES
2.1
FORMAL DEFNITIONS OF MINHASH, OPH AND ООPH
Formal definitions of MinHash, OPH and OOPH are as follows:
MinHash Broder
1997
Broder et al. 2000): the 7th MinHash value of S is defined as:
h MinHash (S) = (m
(1)
0sick
where (S) denotes the ith hashing on S.
One Permulation Hashing
Li et al.
2012 the 7th MinHash value of S is defined
(mn(((()) n if (T(S) n n2, *
1 OPPH (S)
(2)
Emppyy
no element falls in this bin
US*<k
where T(S) denotes the hashing on S and Ω2 denotes ith partition of the rang space of T(S).
One Permutation Hashing with Optimal Densification Shrivastava Hash value of S is defined as:
2017 1: the Tth Min-
h (OPH (mnn(nn (S) if (T() + OSick
(3)
4OOPH (S) no element falls in this bin
where Numiu (1) denotes 2-universal hashing Shrivastava 2017 and j = Nunio
2.2
USE MINHASH VALUES FOR COMPUTING SIMILARITIES
Computing similarities is key step for many applications like duplicate detection (Broder 1997 Henzinger 2006a)), semantic similarity estimation (Chien & Immorlica 2005). frequent pattern mining Buehrrer & Chellapilla] 2008 Chierichetti et (0099) and more. In the ap- plications, the data (e.g., texts) can be viewed as 0/1 binary data (e.g., the absence/present a set. Given two sets, S1 and S2, the similarity is usually measured by Jaccard Similarity, which is defined as S2) = [S] n S2 S/1///1 U S2). For S and S2 with the same hashing, the probability of the two minimum hash values being the same is equal to Jaccard Similarity of Si and S2, which is formally shown as follow:
of a word), which is equivalent
[S S
Pr[M(S]) = A(S2)) =
= S()
(4)
S USS
3

---

Under review as a conference paper at ICLR 2020
Such a property is called Locality Sensitive Hash (LSH) Property [Inyy & Motwani 1998 Charikar 2002). Note that, if h(S1) and h(S2) are simultaneously empty, they are certain to collide, which violates the LSH Property. So must handle empty bins. Given MinHash values of S1 and S2, the J S2) can be approximated as:
J(S = E
= -
(5)
1=1
with 1(x] being the indicator function that takes value when true and otherwise 0.
2.3 USE MINHASH VALUES FOR LARGE-SCALE LEARNING
Large-scale linear learning like training SVM (Fan et al. 2008 Hsich et al. 2008 Joachims 2006) faced with extremely high-dimensional data, w which omphasizes the application of hashing algorithms. Given a dataset (æt, yr vi){ Di=1- Da R , (-1,+1), L2-SVM solves the following unconstrained optimization problem:
min 4
1 w + C
Σ 1=1
mar(1 - y,w x4 0)2
(6)
2
where C' is a penalty parameter.
MinHash can be used to compact the feature vectors reduce the feature dimensionality the dataset is binary (i.e., each feature vector consists of only Os and 1s) (Li et al. 2011). Actually, each feature vector can be viewed then the i-th clement in the set. Thus we can use MinHash values to represent a feature vector. We one-hot. encoding (Coates & Ng 2011; Buckman et al. 2018 for each hash value and concatenale these k values to get the new feature vector. To further reduce the dimension, [L et al. (2010) proposes that hash value (usually 64 bits). Thus the new feature vector is only 2 x k-bit long, regardless of the dimensionality of the original data.
set: if the i-th element of the vector is 1,
use only the lowest (e.g., b=8) bits of each
2.4 USE MINHASU VALUES FOR FAST NEAR NEIGHBOUR SEARCH
Fast near neighbour search is important in many areas like databases (Broder 1997 Fried-
man et. al. 1975) and machine learning (Shrivastava & Li 2012), especially applications with dime-cima data. Given a query S, near neighbour search is return other sets whose similarities with S are more than a threshold.
Shrivastava & Li (0122) proposed MinHash values can be used in near neighbour search in sub-linear time complexity (i.e., without scanning the whole datasct). Specifically, signature for a set is generated by concatenating i MinHash values like this:
Signature(S) = [S); ( hs(S)]
In this way, those similar sets are more likely to have the same signature (It is not true if emply bins occur). So we can build hash tables by using the signatures as indexes and the sets as the val values of the hash table entries. Moreover, to reduce the number of hash table entries, we only concatenate the lowest b bits of & 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 hash tables, and return the union of entries from these hash tables as the query result. For different hash tables, we should use independent hash functions to compute MinHlsh values. Parameters b, L, and & 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 OnnkL) (n is the size of the query set). Shrivastaaa & Li (2014a) proposes that OPH can generate le x L MinHash values only by one hashing with l x L bins, the processing cost of OPH O(n + kL). (O(n) is for hashing on n elements and O(kL) is for filling empty bins).
4

---

Under review as a conference paper at ICLR 2020
3 ALGORITHM
3.1 AMORTIZATION HASHING
A Algorithm 1: Insertion
Input: bins B[-], hash function k(-),
Algorithm 2: Amortization
set
Input: &t bins B[.] after Insertion
Q t output range of ((.)
for i=0; i < k; i+=2 do
Initialize Mf..
if B/}] empty and Bft+1] is non-emply
PlJ..OddMin==ooo
then
for each clement in S do
L Bij.OddMinn B[i+1] EvenMin
V - l(fe)
B(x] non-emply and Bi++1j empty then
+ (12)/
if V%2-1 then
B Bi++] 15++1.
Bij,OddMin
Oddiin min(V, OddMMn))
If empty bins still exist: Densification
if V%2=0 then
L Bij EvenMin mVn B[i] EvenMMi)
B
E
B
E
B
E D
A
D
C
A
B
D
C
D
A
D
C
AB
C
AB
B
DEC
A
D
E
Insertion
Amortization
Collect Values
Figure 2: A toy example of AHash with 5.
To generate & MinHash values, Amortization Hashing (AHash) has two key steps: Insertion and Amortization.
Insertion: As shown in Algorithm 1 and Figure 2 AHash divides all elements into k bins by hashing and each bin maintains one even min and one odd min. Even min refers to the minimum one among all even hash values. Odd min refers to the minimum one among all odd hash values.
A Aorttiaation As shown in Algorithm 2 and Figure 2 AHash pairs up k bins follows: tt and (i + 1 bins are a pair (i 0, 2, .., A }). For pair, the 7th bin called even bin and the (i + 1)th bin is called odd bin. For the pairs with only one emply bin, there are two cases:
If the even bin Be is empty, reassign EvenMin with the even min of the odd bin.
If the odd bin Bg is emply, we reassign OddOddMin with the odd min of the even bin.
For the pairs with two simultaneously non-emply emply bins, we keep them unchanged. fter the amortization, we collect & MinHash values from bins and there are two cases (See Figure
For each even bin with both even and odd mins, delete the odd min.
For each odd bin with both even and odd mins, delete the even min.

---

Under review as a conference paper at ICLR 2020
If there still empty bins, conduct densifying like OOPH, which rarely happens because AHash significantly reduces the empty bins. Formally, for even bins,
m n
T. (e) n #
min (S)
(e( nΩ, = and To T. n + 7th bin is empty and Te (5) n 2g * others
AHash (S) = h
(8)
min (S) n
Emply
j= 1 + (i 1)%2
(9)
where Te (S) (S)) denotes the even (odd) hash values of and Q denotes i-th partition of the range space of TS)). The formula for odd bins is similar.
3.2 TIME AND MEMORY OVERHEAD
For time overhead, AHassh keeps comparable runtime efficiency with OPH, the fastest variant of MinHash. Although cach bin maintains one more hash values than OPH, the additional runtime cost is negligible bocause of the memory access locality of the insortion (two values in a bin). Note that AHash has much less empty bins which require densification compared with OOPH, which can save the lime cost.
For memory overhead, AHah also provides k MinHash values, which is the same HanHash and OOPH. During the Insertion, the cost of storing two hash values in 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 cache (usually larger than 32 KB), the fastest memory.
4 EXPERIMENTS AND APPLICATIONS
4.1 SETUP
We use three publicly available datasets
a) RCV1: The dataset 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 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,555, 191.
c) URL: The datasct is a collection for identifying suspicious URLs. It has 100, 000 sets and the size of the set on average 115. The dimensionality (range space) elements
3, 261
We use two metrics measure the performance:
a) Mean Square Error (MSE) is defined as [E[[ - J) We use MSE to measure the accuracy of computing the Jaccard Similarity.
2P-R b) F1-score is definod as (P+ where is the precision rate and R is the recall rate. We use Fi-score to evaluate the performance of fast near neighbour search.
We implemented all algorithms in C++ which are publicly available on GitHuu. All experiments are conducted on laptop with 2.9 GHZ Intel Core i7 CPU.
Shtrps:/wwww.csie.ntuu www.tnt.tuwwueeeoommmmt cjlin/ http://stttttoo//attssssss////// biia/b.bbbarrmmml httpss//ggttub..cm//Aashheee AHash Aashh

---

Under review as a conference paper at ICLR 2020
4.2
ACCURACY AND SPEED
Table
1: Pairs of Sets
Pairs
JS
[]
S2
Table 2: Time (Second) to compute 256 MinHash val-
A
0.27
750
567
0.34
750
748
Hash MinHash
RCV1
NEWS20
URL
0.44
750
870
3.44
20.45
25.83
PER
0.53
750
751
OOPH
0.024
0.13
0.18
0.61
750
892
AHash
0.025
0.14
0.18
0.71
750
719
0. 0025
0.003
0. 0025
03811
0. 0.000
0020
Klach
MSB
0. 0015
Nisch
MSE
0.002
Zlass
0. 0015
0. 0010
0.100
0. 00001
0. 0005
0. 0005
0. 0000
0000
0. 0..000
128
256
512
1024
2048
128
256
512
1024
2048
128
256
512
1024
2048
Pair A
(b) Pair B
Pair C
0. 000
0. 0000
0. 0.003
Alnah
COET Allons
MSB
000
0. 0.0011
0, 0.002
0. 001
0.001
0. 0005
0000
128
256
512
1024
2048
128
256
512
1024
2048
128
256
512
1024
2048
k
(d) Pair
(e) Pair E
(I) Pair
Figure Average MSE in Jaccard Similarity estimation with varing the number of MinHash values (k). Results are averaged over 2000 repetitions.
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 ics is shown in Table
Figure presents the results about the accuracy of computing similarities with varying (the number of Minhash values). Regardless of the similarity level, AHash more accurate than OOPH and MinHash (e.g., at & = 512, the MSE of AHHash is lower than OOPH by 13. 23.3%%)... For Figure 3 the absolute values of MSE are too small, it's 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 & 512 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 is extremely small, all bins are non-emply. Therefore, AHash has need for amortization. To the other extreme, if A is extremely large, only small portion bins are non-empty and the amortization plays a limited role. Fortunately, with practical and commonly used configuration, AHash presents significant gains.
Table 2 shows that the speed of computing & MinHash values of AHash 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
1000
99.9
98.9
Accuracy
Accuracy (%)
999
Accuracy
99.88
89.8
98
87
87.
96
96. of
10 10"- 10
10
10
10
10'
10
10 10
10
(a) RCV1
(b) URL
(c) NEWS20
Figure 4: SVM test accuracy, We set A as 150 and apply the b-bit hash with as 8.
We use LIBLINEAR (aan et al. 2008) to Irain a Lz-nomarlized SVM to measure the elfectiveness of AHash in reducing the dimensionalitty 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
experiments.
Figure 4 shows that AHash can achieve 99% test accuracies and outperforms OOPH. Com- pared with training with the original high-dimensional data, the training based 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 average is 46.81% lower than OOPH in Figure 4(b). AHash can achieve the satisfied accuracy, close to 100%.
4.4
NEAR NEIGHBOUR SEARCH
0. 125
0.
0.17
0. 120
0.
Et- -1-ooree
F1-Score
0. 115
0.16
010
0.09
0.
0.00
0. 105
0. 1000
0. 04
0.07
0. 0.09
0.06
20
21
22
23
24
25
(a) RCV1
(b) URL
(c) News20
Figure 5: Fi-score of fast near neighbour search. We set is as and apply the b-bit hash with as 32. Results are averaged over 2000 queries.
We apply AHash with the optimization of b-bit hashing Li et 2010) for fast near neighbour search. Given a query set, threshold of the similarity is 0.5, that is, near neighbour scarch 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 near neighbour search. Therefore, we use Fi-score as the metric.
Figure shows that the Fi-score of AHash is significantly higher than MinHash and OOPH on all three datasets. Note that the trend of Fi-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 outperform OOPH and MinHash under most of paramcter settings.
CONCLUSION
We propose Amortization Hashing which can improve the accuracy of One Permutation Hashing and densification strategies without loss runtime efficiency. AHash outperforms the state-of-the-art OOPH in similarity estimating, large-scale learning and fast near neigh- bour searching.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Roberto J Bayardo, Yiming Ma, and Ramakrishnan Srikant. Scaling up all pairs similarity search. In Proceedings of the 16th international conference on World Wide Web, pp. 131-140. ACM, 2007.
Andrei 7. Broder. On the resemblance and containment of documents. In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171), pp. 21-29. TEEE, 1997.
Andrei Z Broder, Moses Charikar, Alan M Frieze, and Michael Mitzenmacher. Mine independent permutations. Journal of Computer and System Scienoes, 60(3):630 659, 2000.
Jacob Buckman, Aurko Roy, Colin Raffel, and Tan Goodfellow. Thermometer encoding: One hot way to resist adversarial examples. 2018.
Gregory Buehrer and Kumar Chellapilla, A scalable pattern mining approach to web graph com- pression with communities. In Proceedings of the 2008 International Conference on Web Search and Data Mining, pp. 15-106.4 ACM, 2008.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the fhiry-fourth annual ACM symposium Theory of computing, pp. 380-388. ACM, 2002.
Steve Chien and Nicole Immorlica. Semantic similarity between search engine queries using temporal correlation. In Proceedings of the 1/th international conference on World Wide Web, pp. 2-11.
ACM, 2005.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Panconesi, and Prabhakar Raghavan. On compressing social networks. In Proceedings of the 15th ACM STGKDD international conference on Knowledge discovery and data mining, pp. 219-221922222 20-2228.222 ACM, 2009.
Adam Coates and Andrew Ng. The importance of encoding versus training with sparse coding and vector quantization. In Proceedings of the 28th international conference on machine learning (ICMI-11), pp. 921 928, 2011.
Rong- En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang- Bann-RRiiLo Wang, and Chib-Jen Lin. Liblinear: A library for large linear classification. Journal of machine learning research, (871))1881111874 2008.
Raul Castro Fernandez, Jisoo Min, Demitri Nava, and Samuel Madden. Lazo: A cardinality-hasee method for coupled estimation of jaccard similarity and containment. ICDE, 2019.
Jerome H. Friedman, Forest Baskett, and Leonard Shustek. An algorithm for finding nearest neighbors. IEEE Transactions on computers, 100(10):1000 1006, 1975.
Monika Henzinger. Finding near-duplicate web pages: a large-scale evaluation of algorithms. In Pro- ceedings of the 29th annual international ACM SIGIR conference on Reseorch and development in information retrieval, pp. 284-291. ACM, 2006a.
Monika Henzinger. Finding near-dullicate web pages: large-scale evaluation of algorithms. In Pro- ceedings of the 29th annual international A ACM SIGIR conference on Research and development in information retrieual, pp. 284-291. ACM, 2006b.
Cho-Jui Hsieh, Kai-Wet Chang, Chih-Jen Lin, S Sathiya Keerthi, and Sellamanickam Sundarara- jan. A dual coordinate descent method for large-scale linear svm. In Proceedings of the 25th international conference on Machine learning, pp. 408 415. ACM, 2008.
Piotr Indyk and Rajeey Motwani. Approximate nearest neighbors: towards removing the curse of dimensionalityy In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604-613. ACM, 1998.
Thorsten Joachims. Training linear syms in linear time. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 217 226. ACM, 2006.
Ping Li. 0-bit consistent weighted sampling, In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 665 674. ACM, 2015.
Ping Li and Christian König. b-bit minwise hashing. Tn Proceedings of the 19th international conference on World wide web, pp. 671-680 ACM, 2010.

---

Under review as a conference paper at ICLR 2020
Ping Li, Arnd Konig, and Wenhao Gui. b-bit minwise hashing for estimating three-way similarities. In NIPS, pp. 1387-1895, 2010.
Ping Li, Anshumali Shrivastava, Joshua L Moore, and Arnd C König. Hashing algorithms for large-scale learning. In NIPS, pp. 2672, 2011.
Ping Li, Art Owen, and Cun-Hui Zhang. One permutation hashing. In NewrIPS, pp. 3113 3121, 2012.
Aushumali Shrivastava. Optimal densification for fast and accurate minwise hashing, In ICML, pp. 3154 3163, 2017.
Anshumali Shrivastava and Ping Li. Fast neighbor search in high-dimensional binary data. In Joint European Conference on Machine Learning and Knowledge Discovery Databases, pp. 474-489. Springer, 2012.
Aushumali Shrivastava and Ping Densifying one permutation hashing via rotation for fast near neighbor search. JCML, pp. 557-565, 2014a.
Aushumali Shrivastava and Ping Li. Improved densification of one permutation hashing, arxiv preprind 14064:1406.44 2014b.
Hsiang-Fii Fu Yu, Cho-Jui Hsieh, Kai-Wei Chang, and Chih-Jen Lin. Large linear classification when data cannot fit in memory. ACM Transactions on Knowledge Discovery from Data (TKDD), (4):23, 2012.
10

---

Under review as a conference paper at ICLR 2020
A
THEORETICAL ANALYSIS
Theorem 1 Unbiased Estimator
Pr[h (Si) = h A.Haa (Sa)
[S S()
(10)
SS U2
E(JAHosh) =J
(11)
where JAHash denotes the estimator given by AHash. Theorem is to show the estimator of AHash following the LSH property and unbiased.
Proof A.1 For convenience, we define some Boolean values:
{
For both 8th bins of S1 and S2, no elements falls them otherwise
Lamp, = uskckk
(12)
Before Amortization, the values of the tth bins of S1 and S2 are the some otherwise
Imats ogick
(13)
1 A -AAllsh (Sz) -Empyy
Pmmp. useck
(14)
otherwise
(o
mata osick
(15)
otherwise
Obviously, for simultancously non-emply bins, AHash following the LSH property:
Bllmpt, 0)
(16)
Nexl, we prove that the Amortization for simullaneously emplyy bins is unbiased:
Temp. = and 14 Temp. = - Temp.t =
1
(j= = +1
[[Imat,il
1 and Immp. 0) E(1 [mat [emp. =
(17)
If Témp. = 1, i.e., there is still the pair of bins which are simultaneously empty ofter Amortisation, we use unbiased Optimal Densification [Shrivastava, 2017) to fill such bins.
Theorem Reducing Emply Bins
E(N < E ((NOP!)
(18)
where Nemp = Eke Timp is the number of simultaneously empty bins.
Proof A.2 LT al. 2012) proves the expectation of the number of simultaneously empty bins of OPH
D 1--1
E(N = v(k) II 1=0
(19)
where |S S2l and D is the dimensionality of the universal hashing function used. The process of OPH can be viewed as randomly throwing balls into bins. For A AHash, becouse & hins are paired up, the process of AHaash can be viewed as randomly throwing f balls into bins. Obviously. Nemp of AHash is smaller than OPH:
E(VAHash)) 55)))((()))))) vk()
(20)
Theorem 3 Improving Variance
Var Var(Joori)
(21)
11

---

Under review as a conference paper at ICLR 2020
Proof A.3 We define two Boolewn values with 1(x) being the indicator function that takes when true and otherwise
Mt* 1(lemp.j = 0 and h2 ha (Si) = h AHHuh (S2)}
(22)
M 14empp. and h3 ( h3 h (S2)}
(23)
The estimator given by AHash and the variance of AHash can be rewritten as follows using these two volues.
JAHach DiM +M,91
1 k ==1
(24)
Var(JAHuah) = E((, Ding + Mf ((((J
(25)
1o
5=1
Theorem proves (F(JAHosh)) = J. Define two notations:
NEmP Tempet
J Tmmp.
(26)
OОPH conditional expectation to simplify variance enalysis. To conveniently compare with 0OPH, we follow method where E(.lm) means E(Ik NAHash E(( Σ MM + (m)m) By expanding.
m). We compute (m)
k (m)) = E ((MP) + (M)))) + E M M,
(27)
E
M (m) + E
M, M,, (m)
Because M and M Boolean values,
&
E ((M (M [m)] = E (M + aM = xJ
(28)
To analyze another three terms, we provide four probability equations for bins before the amortiza- tion.
(k- 11118811 Pr[Jemps = Pe = -/
(29)
Pr[Jemp.j =0) P, =1- Pe
(30)
Pr(Iemp.J =0 and the mins from two j-th bins have one and only one position)
|S:u8al/A-NoPP = P. - x2x (,)
(31)
Pr(Lemp.s =0 ond the mins from two j-th bins have two positions (odd/even))
Pa = Py P.
(32)
Define one notation:
j St Sz
(33)
S. Sz
The values of followingg three terms is proved by classifring different combinations of bins and applying probability equationns and the property of indicator functions.
E
M M/ m(m 1)jsk k
k-2 +J P.P. JJ k-1
2PaP.] S m(m 1)J5
(34)
12

---

Under review as a conference paper at ICLR 2020
E(
Mi MM (m) = 2m(k -m)[ J +
(m (m- 2)JJ
J 1
x P.P. + PaPP
PaPd
m
m
183
(35)
I 2m(k - m)l y +
(m (mJ1)JJ
m
E( M Mj (m) (k. (k-m)(kk -1){
(m - 1
m-- k-1
JJ
JJ k-
1
PPaP.
(t)
(36)
1)1 J (m 1)J3
+J k-1 x P.Pe JJ k-1 x Pypp (k: m)
Hence, we get that
k fmm h(m) k x m(m 1)J3 2m(h: -mm[ 1
(m 1)JJ
m
(37)
J (m 1)J5
+(k m2)(k m 1)[
For OOPH, the veriance is
A-1 Var(Joorn) = E(( [M + MD11)) (F(Joora)).
(38)
k
J=0
M₁ 1 1fTemp. 0 and h
(PPH(S)) (8i) horH (Sz)
(39)
M," 1flemss = 1 and h2 h0OPH (Si) h2 hOOPH (St)).
For OOPH, the conditional expectation
B((
R ΣIM5 M + 1 NOPH = =m) h(m')
(40)
0l((m)
m m²
(JJ J) S and m 2 m'
m
(41)
h(m) $ (mm)) - Vor(J S V Var Var(JooR))
Because AHash reduces Nemp, A Aash using Optimal Densification Shrivastava 2017 lower variance compared with OOPH.
achieve
13


Reviews:
[{"review_id": "r1eEbe2q9H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a bin split strategy for one permutation hashing which reduces the expected number of empty bins. The idea is to use two sets of hashes (odd and even) to make more use of the data. The strategy reduces the variance of existing densification scheme. Experiments show that the proposed method gives lower MSE, good classification accuracy and better NN search performance.\n\nOverall, the idea is interesting, although the improvements will only occur in very much corner cases. The wiring can be improved. The author also use ( ) instead of [] for citations which made the paper difficult to read (among with other writing problems). The theory (and its correctness) is difficult to be justified. The authors are suggested to use plots to verify the theoretical results. \n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "SJgOQ8pTKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*** Summary ***\nMinHash 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.\n\n*** Evaluation ***\nThe paper proposes an interesting idea for approximating set similarities much faster than MinHash. However, I have some issues with the submission.\n\nI 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?\n\nThe 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?\n\nThere 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.\n\n\n*** Further Comments ***\n- The font was changed. It does not match the font of the other submissions.\n- The spacing is tricked in several places, especially in Section 4.\n- Links [1,29] should not be references but footnotes.\n- 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.\n- What does OOPH stand for? It is never stated.\n- Every equation has a number, but none is ever referenced.\n- Math/Equations are part of the text and should be treated as such, i.e., there should be proper punctuation marks.\n- What is a 2-universal hashing?\n- Algorithm 1: \"output range\" sounds like an interval whereas the number of distinct hash values is meant.\n- \"(14) proposed\", no past tense\n- Instead of \"(11) proposes\", please use \"Shrivastava and Li [11] propose\"\n- Why \"Theorem 1\" and \"Proof 3.1\"?\n- Why are the theorems lacking the assumptions and text? They basically consist of equations.\n- Theorem 3 should have a \"less or equal\" instead of a \"strictly less\".\n- Eq. (40): \"0andm\"\n- Why does Proof 3.3 have a end of proof sign (not right-aligned) but the other proofs don't?\n- 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.\n- How are the pairs of sets in Section 4.2 chosen and why only from RCV1? This seems to be the most important experiment.\n- Why is k (and b) fixed to an arbitrary value in the remaining experiments? Please select C within a proper cross-validation.\n- 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.\n- It is nice that the source code is published online, but uncommented c++ code is not really helpful.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1xjvMuC9H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed an efficient minwise hashing method, namely Amortization Hashing (AHash), for solving the issue of the unbalanced loading during hash code generation. Specifically, in AHash, two steps, called Insertion and Amortization, are designed to balance the load in order to reduce the empty bins. In addition, a detailed theoretical analysis was provided. The authors evaluated the proposed AHash on three text categorization benchmarks, i.e., RCV1, NEWS20, and URL, comparing against the previous min-hashing algorithms including OOPH and MinHash. The experimental results show the effectiveness of the proposed hashing method.  \n\nSome comments on this work are listed as follows.\n1. This paper is well motivated and structured, which may serve as a guidance for other works.\n2. Three tasks, similarity estimating, large-scale learning, and fast near neighbor searching reduction, are adopted to validate the proposed AHash. The experimental results show that the proposed method can achieve state-of-the-art performance.\n3. It seems that the effectiveness of the proposed method is OK but not surprising. The improvement of AHash over OOPH is unobtrusive, given the results shown in Table 2, Fig. 3, and Fig. 4.\n4. The authors claimed that more signiﬁcant performance can be achieved when the number of bins is appropriate on the task of computing similarities. Is there any theoretical guarantee for such an appropriate condition?\n5. The proposed method still cannot entirely solve the problem of empty bins, where a densifying operation may also be needed.\nMinor error:\nA typo exists in Eq. (10), where one “)” on the left-hand side is needless.\n\nOverall, the proposed AHash in this work is interesting and seems effective when dealing with the problem of the unbalanced load. However, there still exist quite a few issues in the current version, which need more explanations and clarifications.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1gLNgI95r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new hashing method based on MinHash. It aims to improve the computational complexity of the original MinHash and reduce the error of One Permutation Hashing. The proposed method is mainly assigning bins into paired bins, odd bins and even bins, and obtain two hash values, an even min and an odd min, for each bin. It finally reassigns nearby hash values to empty bins. The paper provides theoretical analyses that show the proposed method gives 1) unbiased estimator; 2) fewer empty bins 3) smaller variance. Finally the paper did some experiments on several applications including SVM and nearest neighbor search. The results show improvement over MinHash and OOPH. \n\nThe paper is mostly well written and easy to read. I have a few questions. \n\n1. My main concern is the lack of proof details. I tried to read through Proof 3.1. However, I found it is hard to follow. I'd suggest to add more details and explaination in the proof. For example, how is Eq. (17) obtained? \n\n2. The floor symbol \\lfloor, \\rfloor in Eq. (9) seems to be misused. It seems that the paper wants  $\\lfloor n/2 \\rfloor$ to return the largest even integer that is less than or equal to the given value, n. Right?\n\nOverall, I vote for weak accept as the proposed is novel and the theoretical results seem reasonable to me. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a load-balanced hashing called AHash that balances the load of hashing bins to avoid empty bins that appear in some minwise hashing methods.
Reviewers found the work interesting and well-motivated. Authors addressed some clarity issues in their rebuttal. However the impact appeared quite limited, and the experimental validation limited to few realistic experiments that did not alleviate this concern.
We thus recommend rejection.
Decision: Reject