SignRFF: Sign Random Fourier Features
Authors: Xiaoyun Li
Ping Li
Venue: NeurIPS 2022 Accept (2022)

Abstract: The industry practice has been moving to embedding based retrieval (EBR). For example, in many applications, the embedding vectors are trained by some form of two-tower models. During serving phase, candidates (embedding vectors) are retrieved according to the rankings of cosine similarities either exhaustively or by  approximate near neighbor (ANN) search algorithms. For those applications, it is natural to apply ``sign random projections'' (SignRP) or variants, on the trained embedding vectors to facilitate efficient data storage and cosine distance computations. SignRP is also one of the standard indexing schemes for conducting approximate near neighbor search. In the literature, SignRP has been   popular and, to an extent, becomes the default method for ``locality sensitive hashing'' (LSH). 

In this paper, we propose ``sign random Fourier features'' (SignRFF) as an alternative to SignRP. The original method of random Fourier features (RFF) is a standard technique for approximating the Gaussian kernel (as opposed to the linear cosine kernel), in the literature of large-scale machine learning. Basically, RFF applies a simple nonlinear transformation on the samples generated by random projections (RP). Thus, in the pipeline of EBR, it is straightforward to replace SignRP by SignRFF. This paper explains, in a principled manner, why it makes sense to do so. 

In this paper, a new analytical measure called \textbf{Ranking Efficiency (RE)} is developed, which in retrospect is closely related to the ``two-sample mean'' $t$-test statistic for binomial  variables. RE provides a systematic and unified framework for comparing different LSH methods. We compare our proposed SignRP with SignRP, KLSH (kernel LSH), as well SQ-RFF (which is another 1-bit coding scheme for RFF). According to the RE expression, SignRFF consistently outperforms KLSH (for Gaussian kernel) and SQ-RFF. SignRFF also outperforms SignRP in the relatively high similarity region. The theoretical comparison results are consistent with our empirical findings. In addition, experiments are conducted to compare SignRFF with a wide range of data-dependent and deep learning based hashing methods and show the advantage of SignRFF with a sufficient number of hash bits. 


SignRFF: Sign Random Fourier Features
Xiaoyun Li, Ping Li
LinkedIn Ads 700 Bellevue WA NE, Bellevue, WA 98004, USA
com
Abstract
The industry practice has been moving to embedding based retrieval (EBR). For example, in many applications, the embedding vectors are trained by some form of two-tower models. During serving phase, candidates (embedding vectors) are retrieved according to the rankings of cosine similarities either exhaustively or by approximate near neighbor (ANN) search algorithms. For those applications, it is natural to apply "sign random projections" (SignRP) or variants, on the trained embedding vectors to facilitate efficient data storage and cosine distance computations. SignRP is also one of the standard indexing schemes for conducting approximate near neighbor search. In the literature. SignRP has been popular and, to an extent, becomes the default method for "locality sensitive hashing" (LSH).
In this paper, propose "sign random Fourier features" (SignRFF) an alterna- tive to SignRP. The original method of random Fourier features (RFF) is standard technique for approximating the Gaussian kernel (as opposed the linear cosine kernel), in the literature of large-scale machine learning. Basically, RFF applies a simple nonlinear transformation on the samples generated by random projections (RP). Thus, in the pipeline of EBR, it is straightforward to replace SignRP by SignRFF. This paper explains, a principled manner, why makes sense to do so.
In this paper, new analytical measure called Ranking Efficiency (RE) is de- veloped, which retrospect is closely related the "two-sample mean" 1-test statistic for binomial variables. RE provides systematic and unified framework for comparing different LSH methods. We compare our proposed SignRP with SignRP, KLSH (kernel LSH), well SQ-RFF (which is another 1-bit coding scheme for RFF). According to the RE expression, SignRFF consistently outperforms KLSH (for Gaussian kernel) and SQ-RFF. SignRFF also outperforms SignRP in the rel- atively high similarity region. The theoretical comparison results are consistent with our empirical findings. In addition, experiments conducted compare SignRFF with a wide range of data- deta-dependent and deep learning based hashing methods and show the advantage of SignRFF with sufficient number of hash bits.
Introduction
We study the search problem with data points in Rd. Let X denote the database consisting of data points. Given a query data point q. the task is to find the a similar data point in X. For the purpose of discussion, we denote
data points in X by and y. For simplicity, we consider the data points are normalized, i.e., ||>:| = || = Therefore, the "cosine" similarity between æ and y is simply p cos(æ. 3) = Σi E,y. We also denote the Gaussian kernel between and y to be k(p) k(x, y) = (1-p)) where 7 > 0 is tuning parameter. In this paper, we study binary coding algorithms for efficiently finding near neighbors based similarities related to p and k(p). In particular, our methods are based on random projections and (quantized) random Fourier features.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

1.1 Random Projections (RP) and Sign Random Projections (SignRP)
Denote by w d-dim vector of random i..dd entries, i.e., w; ~ ((0, 1), = 1 to The idea of random projections (RP) is to compute the inner product w x between and the data vector æ and the same for w² y. It is easy to see that [[[(w""=)) (w) y)] = cos(æ, y) = p. The idea of sign random projections (SignRP) is to keep only the signs of the projected values:
SignRP: hap(T) sign(w" x),
hzr = sign y).
(1)
There a chance that the two hash values, i.e., the signs (x) and hxr(y). will be equal [16, 5]:
(() = hnr(y) = cos
(2)
Interestingly, if wy is sampled from a Cauchy distribution (instead of Gaussian), then the collision probability is closely related to the popular Chi-square similarity instead of the cosine [37].
1.2 Binary Code and Approximate Near Neighbor (ANN) Search
The method of sign random projections (SignRP) and the collision probability (2) have been widely used [5] as a standard hashing method for locality sensitive hashing (LSH) in the context of approxi- mate near neighbor (ANN) search [21]. Basically, we can generate b independent hashes to form a hash table of size 2h (c.g., b = 20 means hash table with million buckets). For query one can compute hash values h (q) to form a b-bit code and retrieve all data points form X which fall into the bucket corresponding to the I-bit code. To improve the retrieval accuracy, typically multiple hash tables are used to return the union of retrieved results from all the tables.
SignRP is one example of a broad class of method based on binary coding for ANN, That is, for each data vector x Rd, we hash it into length-b binary 0/1 vector h(x) E {0, 135, where the geometry of the data should be well preserved in the hamming space. Searching with binary codes has been widely applied in many applications, such as large-scale image retrieval [65, 17, 26, 20, data), 44, 45, 46, 61, 72, 68]. Besides the benefit of storage saving (especially for high-dimensions compressing data binary can also significantly speedup the retrieval process. In this paper, our analysis and evaluation will focus on the hamming ranking approach which has been widely applied in image/video retrieval [26, 17, 49, 50, 4, 56, 70, 18, 47, 52], where we conduct exhaustive search in the hamming space. In fact, SignRP is also used by other ANN systems such as graph-based ANN as a crucial component to save the storage and speedup distance computations [76, 75].
1.3 Random Fourier Features (RFF) and SignRFF (Our Contribution)
Nonlinear kernels have been proven to be effective in many machine learning tasks [57, 2, 19]. See [33] for a study which empirically compared specially designed nonlinear kernels (i.e., "tunable GMM kernels") with deep nets and boosted trees. In this study, we focus on the Gaussian kernel:
k(p) k(I, y) e-> (1-p))
One can also utilize random projections to approximate the Gaussian kernel via the random Fourier features (RFF) [55, 54]. For data vectors x, y E IRd, the RFF for the Gaussian kernel is defined as
RFF:
F(x) = cos( (w" T x + T), Fly) = cos( w y + +T),
(3)
where w 70 Ia) and
2ni where Ia is the identity matrix. It holds that [[F(()) = k(x,,, /2, 2,, i.e., the non-linear kernel can be preserved in expectation by the linear inner product of RFF To approximate the kernel, we generate b independent RFFs for each data point using i.i.d. W1,- .... Whb and 7ı..., To. which can be used for subsequent learning tasks. Additionally, it was shown in [32] that the normalized RFFs (NRFF) can substantially reduce the variance of RFF.
This method has lead to many applications in large-scale learning where one trains linear models on RFF to approximate non-linear kernel machines [71, 9, 63, 1, 62, 64, 39J. To extend RFF to retrieval tasks, in this paper, we propose SignRFF by keeping only the signs of the random Fourier features:
SignRFF:
heign (x) = sign(F(a)) sign(cos( www x +)).
(4)

---

We skip the same step for ssign (t). Note that, this is different from the earlier work called "SQ- RFF" [53] which proposed construct binary codes from RFFs using stochastic binary quantization:
SQ-RFF:
l - (Fg)(F( + E) - sign(cos(w x + + +
(5)
where ç ~~ Unif(-1,1) is random perturbation. To extent, idea inspired by [36], which showed that the stochastic perturbation in [11] for quantized random projections was not needed. will show theoretically and empirically that SignRFF is better than SQ-RFF. In
In this study, particular, we propose a new evaluation metric named "ranking efficiency" (RE) to serve as a unified measure to analytically compare the search performance of different LSH methods. Under this metric, SignRFF consistently outperforms various other LSH schemes. Our experimental study also confirms that RE is strong predictor of the empirical search performances.
1.4 Other Related Methods
Quantization methods for random projections have been extensively studied in the literature, e.g.. [16, 5, 11, 13, 36, 34, 41, 40]. Quantized methods for random Fourier features have also been heavily- studied [53, 74, 43, 43, 42]. In the meanwhile, there have been many works which have focused on learning data-dependent binary hash codes, through different objective functions. Examples include Iterative Quantization (ITQ) [17], Spectral Hashing (SpecH) [65] and Binary Reconstruction Embedding (BRE) [26]. Recently, some unsupervised deep learning based methods have been proposed. many of which are, to some extent, "task-specific" for cross- maass-ooaovvidd/immaee retrieval, implemented based on some deep models like the autoencoder and VGG-16 [45, 12, 38, 69, 18, 47, 52], showing promising performance in image retrieval tasks by taking advantage of the complicated model structures (e.g., CNN layers) [69, 52].
2 Background: Locality- Hashing (LSH)
As mentioned earlier, in large-scale information retrieval, exhaustive search of the exact nearest neighbors is usually too expensive. common relaxation in this setting is the Approximate Nearest Neighbor (ANN) search [21], where we return "good" neighborhood of a query with high probability. In this paper, we consider the search problem with data points in Rd X denotes the database consisting of n data points, and q is query point. Recall that x, y two data points with = (2. x. y).
Definition 1 (Š-neighbor). For a similarity measure S Rd Rd + R. the S-neighbor set of q is defined as (æ E X S(xx q) $).
Definition 2 ((c, Š)-ANN). An algorithm probability at least 8, for 0 < 1, if there exists an S-neighbor of q in X. A returns c5 nnighhob of q. where 8 is a parameter.
a (c, -YNN method provided the following: with
One popular family of hash functions satisfying Definition 2 is the Locality-Sensitii Hashing (LSH), whose general definition is provided below.
Definition 3 ([21)) A family of hash functions H. is called ($, c$, P1.P2) A-l--oalttyysessiiiee for similarity measure S and 0 < e < 1, if for Vx, y E IRd and hash function uniformly chosen from H. it holds that: 1) If (ax, y) 2 S, then P(h(x)) h(y)) 2 pı; 2) If ((xx, y) S cS, then P(h(x=) = h(y)) S P2, with p2 < P1.
A key intuition of LSH is that, similar data points will have a higher chance of hash collision in the Hamming space. One example of LSH method, associated with the cosine similarity, is given by the SignRP approach as in (1). Note that the hash collision probability (2) is increasing in p. which, by Definition 3, is the key to ensure the locality sensitivity of SignRP.
Compared with the data-dependent methods (e.g., as mentioned in Section 1.4), LSH has several advantages. Firstly, although date-dependent procedures can provide improved performance with fewer binary codes, a known weakness of many of these mechanisms the performance bottleneck when we increase the code length [53, 24]. On the other hand, the search performance of the data-independent LSH would keep boosting with larger (c.g., < 128 bits) cannot achieve desirable level of search accuracy for practical purposes, using
many scenarios where short codes
3

---

longer LSH codes could be more favorable. Moreover, LSH is very simple to implement (only with random projections), while data-dependent methods require additional optimization//raiiingg and longer inference time (e.g., for deep networks). Lastly, LSH enjoys rigorous theoretical guarantees on the retrieval performance. Therefore, LSH has been a popular hashing method with many practical applications for decades [3, 11, 58, 59, 31, 51, 14, 7, 35, 73, 28, 30, 10, 6, 66, 67].
Kernelized LSH (KLSH). The SignRP (1) approach is based on linear random projections. Recall the Gaussian kemnel function defined for æ, E R as k(p) = k( y) = -->9(1-)), where y hyper-paraameter. Let V : Rd + F be the feature map to the kernel induced feature space F. To incorporate non-linearity in the hash codes, [27] proposed Kernelized I Locality-Sensitie Hashing (KLSH) by conceptually applying SignRP (1) in the kernel induced feature space F, i.c., h(x) sign(w" (x)).. As in many cases (e.g.. for the Gaussian kernel) the map v/ cannot be explicitly identified, KLSH proposes to approximate the random Gaussian distribution using data through the Central Limit Theorem (CLT) in the Reproducing Kernel Hilbert Space. Specifically, we first sample m data points from X to form a kernel matrix K, then uniformly pick t points from [1, ..., m| at random to approximate the Gaussian distribution. After some algebra, the hash code for
E IRd is finally computed as
m
KLSH:
(KLSH(()) sign( Σ r())((a)
where r - K-1/22,, and e, E {0, 11 has ones at the indices of the i selected points. Since KLSH uses a pool of data samples approximate the Gaussian distribution, the hash codes are in fact dependent in implementation. Thus, a performance bottleneck has also been observed for KLSH as b increases [24], similar to many data-dependent methods. See Appendix D for more explanation.
Embedding based retrieval (EBR) has become an mainstream in industry practice, owing to the matured technologies in deep representation learning and approximate near neighbor (ANN) search. For example, [15] described how to use two-tower model to train embedding vectors using click- through data, and then use ANN techniques the serving phase to retrieve ads candidates based on the cosine similarities of embedding vectors. [15] demonstrated the advantages of EBR in terms of improvements in CTR in industry, universal problem arises, that is, how to effectively store the embeddings and efficiently compute cosine similarities. SignRP and variants such as [13, 36, 34, 41] would be an option for EBR for multiple purposes: data reduction, efficient distance computation, well indexing for ANN. On the other hand, we can use hashing schemes (SignRP, KLSH, SQ-RFF, etc.) which are related to the Gaussian kernel, to replace SignRP, Of course, one also choose hashing methods for similarities which are not cosine or Gaussian. One such example is the generalize min-max kernel and consistent weighted sampling (and their variants) [48, 22, 32, 35).
rate) and ads revenue. As EBR has become the standard practice
3 Locality-Sensitiv Hashing From Random Fourier Features
Random Fourier feature (RFF) [55, 54] is a tool for alleviating the computational bottleneck of standard kernel methods. For data vector æ E Rdd recall (3) the RFF for the Gaussian kernel as
RFF:
F(x)) = cos(wv x: T):
where w 2 and ~ Unif(0.25) 2n) where I is the identity matrix. It holds that ((F(x) ((F())(())) F(y)] k( /)/ The probability distribution RFF is given as follows.
Lemma ([43)). For two normalized data points x. y with cosine p. let F(.) be the RFF defined as (3). The joint distribution of za F(x)) and by = F(y) is
Σ (a an + 2kT) + (a + +ay + 2KT)
f(z,, zylp)
cos- (zy), and dh (.) is the p. of N NO, with o 22(1 -ph: Furthermore, ([ssign(F(a)) (x))))igg(FFF (F(y)) is an increasing function of p.
where o- cos ((z), ai = cos

---

3.1 SQ-RFF with Stochastic Quantization
To extend RFF to efficient search algorithms, [53] designed mapping [-1,1] {0, 1] to construct binary codes from RFF. For æ E 12, the code is produced by stochastic quantization (SQ):
SQ-RFF:
hx)(()) = sign(F(x)) + f) = sign(cos(w" +) +
where { is random perturbation from Uni Effectively, the so-called SQ-RFF applies a sampling procedure where we first compute the RFF = cos(w) 2 + 7), and then assign it to 1 (otherwise -1) with probability ||+=|, This approach has been used in [74, 43] for large-scale low-precision kernel training. The collision probability "SQ-RIF" given below.
Theorem (153)) For SQ-RFF for normalized x; y E Rd with cos y) = p. holds that
00
PSQ(p) == ((hso( = hsq(y)) =
(7)
4s² -1
The SQ-RFF in (5) is (k, ck, PsQ(P1), PsQ (p2) -locality sensitive w.r.. similarity measure k(-), where P1 log(k)/> + and
Proposition 1.
/ ++++1
Proof. According to Definition 3, RQ-RFFIT is sensittyse w.r.t. p because (7) is an increasing function of p. Hence, it is also locality- w.r.t. the kernel k(p) by the monotonicity of k(p). The P1 and P2 are derived by inserting into the inverse map of the kernel function.
3.2 SignRFF: Why Not Drop the Noise?
The SQ-RFF has been a standard approach for constructing binary codes from RFF for over a decade. Yet, is the additional perturbation added to the RFF before binarization really necessary? Motivated by this question, we propose simpler coding strategy directly take the sign of RFF (i.e., deterministic quantization) and remove the noise Formally, the SignRFF approach is defined by
SignRFF:
haign (a) = sign(F((x) sign(cos(uu (wT x + 7)).
Operationally, SignRFF extremely convenient. At the first glance, it may appear bit surprising that this simple scheme has not been studied in literature. We believe of the reasons might be that the theoretical correctness of SignRFF was hard to justify. Based on the joint density function of RFF, show that SignRFF indeed belongs to the LSH family.
Proposition 2. The SignRFF (4) is (k, ck, Paign (P1), Peign (P2)) locality sensitive w.r.t to k(.), with Pi = log(())) loog(k)//?? + and log(ck) + 1,, with collision probability
Psign (p) = Phhssgn (x) = hsign = (.'
flee, Zy zylp)da
(8)
where (Zn, Zylp) is the density function of RFF given by Lemma 1.
Proof. By Definition 3 and the monotonicity of k(p), it suffices to show that the collision probability, P Paign (p), is increasing in p. This immediately follows from Lemma that
E[sign(F(z)) (Fiz)))igg(((FFF [F))) Psign (p) (1 Psign (p)) PPsign (p)
an increasing function in p.
Compared with SQ-RFF, the proposed SignRFF exhibits less "variation" brought by the stochastic sampling procedure. In fact, in the kernel approximation problem, it has been shown that stochastic rounding has higher variance due to the noise & which hurts the kernel estimation accuracy [43]. While such comparison is not immediately obvious for the task of nearest neighbor search, next we will show that dropping the extra noise in the binary codes indeed leads to improved search performance, measured by new metric specifically for the binary hash codes from LSH.
5

---

4 Ranking Efficiency (RE): A New Measure for Search Performance
In this section, we systematically compare the above LSH methods (SignRP, SQ-RFF and SignRFF) from a analytical point of view. Before we start, we first provide some analysis of KLSH introduced in Section 2 which will also be included in our comparison.
Collision probability of KLSH. In our theoretical analysis, we assume for KLSH [27] that the Gaussian projection in the kernel induced feature space F is truly random (recall in practice we use data dependent approximations). That is, KLSH "ideally" performs SignRP in the kernel space: 1ILS (ar) sign(w" (a)) where Vi is the feature map to F and w is a random Gaussian vector with proper dimensionality. Since (ax) (g)) = k( y), applying (2) in F. we obtain the collision probability
PKLSH (p) == P(hKLSH (a) h hKLSH(U)) = CDS (e cos--1ee (1-7(1))))
π
Remark 1. Again, we emphasize that due to the dependence among KLSH hash codes resulting from its implementation, in practice the collision probubility of KLSH would be different from (9).
Proposition 3. KLSH is (k, ck. 1 (()
((ck llocality sensitive w.r.t. k(-))
In Figure I, we plot the theoretical hash collision proba- bilities of the four hashing algorithms as in (2), (7), (8) and (9). We see that SQ-RFF has highest collision proba- bility. Recall Definition of the (kt, ck, P1. p2) L It is known [21] that one can construct an LSH data structure
0.1
0.9
collision prob
0.8
n...........
0.5
with the worst case query time On R), where R == log is called the LSH efficiency, which has been used in liter-
log P1
0.7
SgnRP
SigRRFF
ature, e.g., to compare SimHash vs. MinHash [59]. How- ever, since the LSH efficiency only considers the first moment and is based on the a worst case analytical bound, it may not well explain/predict the practical search perfor- mance. See Appendix for related discussion.
0.6
KLSH
7 5
0.5
0
0.5
p
Figure I: Hash collision probabilities.
4.1 Ranking Efficiency
We now introduce the concept of ranking efficiency, which allows us to better compare different LSH methods, theoretically, in terms of search performance. As we will see, the new metric shows the superiority of SignRFF over SQ-RFF, and provides insight on comparing (linear) SignRP with non-linear LSH methods (e.g.. when is SignRFF advantageous?). The definition is motivated by the fact that the effectiveness of LSH binary codes in nearest neighbor retrieval is essentially determined by how well it can preserve the ranking of the true similarities in the Hamming space. Suppose æ and y are two data points in the database, and q is a query with Pa = cos(q. x) ), Pa = cos (q. y). Assume is closer than y to the query q, i.e. Pa Py. By the property of LSH (Definition 3), know that the hash collision probability Pz > Pv- For an LSH hash function h, define the corresponding collision probability estimators
P Σ ((h)(z)) = h.(g)), P, b (1)()))=1( ==1
Now, the problem becomes comparing Pu and p, estimate the true ranking of pa and py- We consider the event of obtaining a wrong similarity comparison from our estimation, i.e. P. S pg. Obviously, higher probability implies worse search accuracy, as we are more likely to retrieve the wrong neighbor y. Denote E, [[)()(x)) h(q) E, = E[i(h(y) = h(g) and
V2
Vay
Cov(1 = h(g)), (((()) = h(g)))) -
By the Central Limit Theorem, as Vg
Vzy
fr ~ N'
Ex
b + so asymptotically, we have that
2/b).
This approximation would be good
B.y
E,y
with sufficiently large e.g. b b2 30. In this regime, we have
Vb(E.. Eyy VV2 + V,, 2V ky
P(pe S py) P(pe py S 0) 00==1-1 11 o
(10)

---

where ((-) is the c.d.f. of standard normal distribution. Based on this characterization, we formally define the ranking efficiency as follows.
Definition 4 ((p,c) Raankkngg Efficiency (RE)). For LSH method, let the hash collision probability
cosine p and op be and Ec. respectively, with S c < Let E(1 E). Ve Ec(1 Ec).
The (p, ra-rannn efficiency (RE) is defined as
Ec VV + Ve
Ranking Efficiency:
RE
(11)
Remark 2.
In most cases, we may care more about large e. values (e.g., = 0.95) which corresponds similar data points with higher chance of reversed ranking.
Remark 3. The covariance Vay in (10) is in general intractable which depends on the specific data and y- We assume that it has same relative impact the RE values and drop from the definition for simplicity. The RE, when multiplied by Vb, is equivalent the 2-score in a two-sample 2-test.
Higher RE implies smaller probability of (10), which more favorable. For all the LSH methods. the Fg and Fry are concretely the collision probabilities given in (2), (9), (7) and (8), and V Eg E2 F.,). Vy = (1 Fry) from the binomial distribution, respectively.
4.2
Analytical Comparison of LSH Methods Through Ranking Efficiency
x
x10=2
x10
1.5
ranking efficiency
0.3 c 0.95
SgnRP SgaRFF
ranking efficiency
0.5 c 0.95
SignRP SignRFF
ranking efficiency
P
0.7 = 0.95
x.
KLSH
S0 RFF
SignAP SignAFF KLSH SC-RFF
0.5
2
4
2
3
4
2
3
4
x10
x10'
1.5 x10
= 0.95
ranking efficiency
ranking afficiency
ranking efficiency
0.9
0.95
SignRP SignAFF KLSH
SignRP
SignRFF
0.5
SignRFF KLSH SO-RFF
SignRP
KLSH SO-RFF
0.95
0.95
SC RFF
2
Figure 2: Ranking efficiency (Definition 4) of different LSH methods with various at 0.95.
Next, we leverage Definition& 4 to theoretically compare different hashing methods. In Figure 2, we provide the RE of (lincar) SignRP, KLSH, SQ-RFF and SignRFF at different p level, which covers the cases in empirical study (Section 5). We present the plots for 0.95, and the conclusions are the same for other c values. We observe that:
Comparing Non-linear LSHs. Firstly, compared with the previous RFF-based approach SQ-RFF, the proposed SignRFF uniformly more efficient at all p. verifying its superiority. Compared with KLSH, SignRFF is more efficient when is large (e.g., >>> 2) in all plots, while KLSH tends to be more efficient only with small 7
When should prefer non-linear LSH? We see that when P high (e.g., p >>> 0.8), with proper tuning, kemel methods (e.g.. SignRFF) can be more efficient than SignRP. However, if the target p is small (e.g., p < 0.7). SignRP becomes more favorable, even for best tuned non-linear LSH. In other words, SignRFF is hetter than SignRP on datasets where the near neighbors are close to each other, with high similarity/short distance.
The ranking efficiency measures the search accuracy for a given p level. In practice, a dataset contains many sample pairs with different p. Our experiments in the next section show that the performance
7

---

is largely consistent with the prediction at the "average p" level. That said, ranking efficiency may provide a convenient way to choose the proper LSH method based on the data of interest.
5 Experiments
We conduct experiments to demonstrate the effectiveness of our approach and justify that ranking efficiency indeed provides reliable prediction of the empirical search accuracy.
Datasets. We use three popular benchmark datasets for image retrieval. The SIFT dataset [23] contains IM 128- dimensional SIFT image features, and 1000 query samples. The MNIST dataset [29] contains 60000 hand-written digits. The CIFAR dataset [25] contains 50000 natural images and we use the gray-scale images in our experiments. For these two datasets, we randomly choose 1000 samples from the test set as queries. In addition, when comparing with VGG-16 [60] based deep methods, following prior literature (e.g-1699, 52]), we use the 4096-d features from the last fully connected layer of the pre-trained VGG-16 16 network as the imput data for shallow methods for fairesss. This dataset is called "CIFAR-VGG" VGG". On all datasets, the data points are normalized to have unit norm. In Figure 3, we report the average cosine between queries to their N-th nearest neighbor, which can be approximately regarded the "target p level" when we compare the ranking efficiency (e.g.. 0.95 for CIFAR).
CIFAR
0.9
SIFT
0.0.
MNIST
0.7
CIFAR-VGG
0.6
100
10
102
103
# of nearest neighbors
Figure 3: Average p to the N-th neigh- bor on four datasets.
Methods and Evaluation. We compare the following unsupervised hashing methods: 1) SignRP [5], defined by (1) with random Gaussian projections: 2) Iterative Quantization (ITQ) [17], which finds rotations to minimize the quantization error of mapping the randomly projected data to binary; 3) Spectral Hashing (SpecH) [65], which is based on quantizing the values of analytical eigenfunctions computed along principal component directions of the data; 4) Binary Reconstruction Embedding (BRE) [26], which explicitly minimizes the reconstruction error between the original distances and the Hamming distances. We use 1000 random samples for model training as suggested by [26]: 5) KLSH [27] as in (6), with m = 500 random samples for formulating the kernel matrix and = 50 samples for the CLT Gaussian approximation, more accurate than (300, 30) recommended in [27]; 6) SQ-RFF [53] given in (5), binary codes from stochastically quantized RFF; 7) Our proposed
SignRFF method (4) with deterministic quantization from RFF For methods (5) (7) involving Gaussian kernel, we tune on a fine grid over 0.1 ~ 5 and report the best result.
For each tested method, we generate binary codes and find neighbors based on Hamming distances. After running each algorithm, the Hamming ranking returns R estimated nearest neighbors to each query. Define N the number of ground truth neighbors. For each query point, the ground truth nearest neighbors are set by ranking the top N = 100 smallest Euclidean distance (top-100 largest cosine similarity). We report the average recall or precision over 1000 queries. The search recall # mae neighbors in R retrieved points and
and precision (the higher the better) are defined as recall R
precision @R
# neighbors in It retrieved points
Note that recall @N is equivalent to precision@N @.
R
5.1 Results
In Figure 4, we report the recall@ 100 (precision @ 100) against the number of binary codes by
On SIFT and MNIST, data-dependent methods (ITQ, SpecH, BRE) perform well with low bits, but the recall does not improve much after > 100 200. Yet, their recall level too low (c.g. < 0.3 on SIFT and CIFAR) for real-world tasks, which is a known limitation of these methods. When 2 256, L.SH-type methods start to dominate. On CIFAR, Rig and KLSH outperform all the data-dependent methods even with low bits.
On all three datasets, SignRFF is substantially better than SQ-RFF with all b. Due to dependence, KLSH has higher recall than SignRFF when b is small (e.g., < 256), but is beaten by FignRFF with more bits. The gap is significant and consistent when b is as large as 512, where SignRFF achieves the highest recall on all three datasets.
8

---

0.6
0.6
0.8
SIFT
CIFAR
MNIST
recall@ 100
0.4
SignRP
recall@ 100
0.4
SignRP
recall@116
0.6
SignRP
ITC
TTQ
ITQ
SpecH
SpecH
0.4
Spech
BRE
BRE
BRE
0.2
SQ-RFF
SO-RFF
SC-RFF
KLSH
KLSH
SignRFF
SignRFF
SignRFF
500
1000
500
1000
500
1000
bits
bits
bits
Figure 4: Recall @ 100 b. Note that in our case, recall @ 100 is equivalent to precision @ 100.
SIFT
CIFAR
0.8
SignRIP ITO
SignRP
SignAP
recall
ITQ
recall
ITQ
SpecH
SpecH
0.6
SpecH
BAE
BRE
BRE
SO-RFF
0.4
SQ RFF KLSH
KLSH
KLSH
SignRFF
SignRFF
SignRFF
500
1000
1000
1000
retrieved neighbors
retrieved neighbors
of retrieved neighbors
CIFAR
0.8
0.8
0.8
SignRIP
-..-- SiinRRP
SignRP
recall
0.6
ITQ
recall
0.6
recall
ITQ
SpacH
SpooH BRE
0.4
BRE
0.4
BRE
0.2
SIFT
KLSH
SQ-RFF
0.2
SQ RFF
KLSH
0.4
MNIST
KLSH
SignRFF
SignRFF
SignRFF
0.2
500
1000
500
1000
500
1000
# of retrieved neighbors
# of retrieved neighbors
of retrieved neighbors
Figure 5: @ vs. # of retrieved neighbors R. 1st
512. 2nd row: b 1024.
In Figure 5, we present the recall versus the number of retrieved neighbors, with = 512 and b = 1024. In general, SignRFF performs the best on all three datasets with a sufficient number of bits. Due space limitation, we report search precision results with consistent conclusions Appendix A, which also includes discussion on the practical implementation and efficiency.
Comparison with Deep Hashing. We provide experiments on the CIFAR-VGG dataset using recent unsupervised deep hashing method, the Contrastive Information Bottleneck (CIB) [52], which uses VGG-16 pre- pre-trained model the backbone. We apply the same training setting as in [52]. Note that, CIB is actually not designed to find the most similar data points. Instead, by using techniques like cropping and rotation in CNN, CIB aims finding data points with the same label as the query. which does not necessarily imply high similarity. Hence, to favor CIB, in this experiment we expand the range of true neighbors of query to the top-1000 1000 most similar points the database in [52] (see Appendix C for detailed discussion). From the results in Figure 6, we observe the following:
SignRP
recali recall@1000 1000
0.6
0.6
SQ-RFF
recall
KUSH
0.4
0.4
SignRFF
SignRP
0.2
SQ-RFF
0.2
CIFAR-VGG
KLSH
SignRFF
CIFAR-VGG
0
500
1000
0
500
1000
bits
of retrieved neighbors
Figure 6: Left: Recal @ 1000 (precision 1000) vs. b. Right: Recall vs. retrieved points, 1024.

---

From Figure 6, CIB performs the best when 6 < 64, illustrating the benefit of deep hashing with short codes. Yet, the recall is only 0.3~0.4, and does not improve with more bits. When b 2 256, SignRP, SignRFF and KLSH provide much higher recall than CIB.
Due to the dependence among codes, KLSH performs the best on this dataset with short codes. SignRFF again consistently improves SQ-RFF, and surpasses KLSH with b 1024.
5.2 Ranking Efficiency is Predictive Measure of Search Accuracy
Firstly, as shown in Figure 3, the average p between each query and its near neighbors is around 0.7, 0.8, 0.9 and 0.95 for SIFAR-VGG. MNIST, SIFT and CIFAR, respectively. The theoretical RE in Figure suggests that compared with SQ-RFF (blue), SignRP (light green) would perform better on MNIST and CIFAR-VGG similarly on SIFT, and worse on CIFAR. This aligns very well with the recall curves in Figure 4 and Figure 5. Here we use SQ-RFF vs. SignRP as an example; similar alignment holds for comparing other methods. To make more detailed justification, in Figure 7, we additionally provide the recall against the Gaussian parameter 7, In Figure 2, the RE curves predict that KLSH should perform better with small 7 while SignRFF more powerful with larger y. This matches the empirical evidence, e.g., for KLSH vs. 2.5 for SignRFF on SIFT to reach highest recall.
Our results verify that: 1) the ranking efficiency to compare different LSH methods in practice; 2) kernel based LSH (e.g.. the proposed SignRFF) is more favorable than the linear SignRP method in high similarity region.
be used informative and effective measure
0.5
0.5
0.7
recall@100
100
0.4
recall@100
0.4
recall@100
0.6
0.3
0.5
SignRP
SignRP SO SOFRFF
.-e- --ignRR
KLSH
CIFAR
KLSH
0.4
KLSH
-SO-FFF
MNIST
SignRFF
SIORFFF
SignRFF
0.2
0.1
0.3
0.5
1.5
2
2.5
3
1
2
0.5
1.5
2.5
3
Figure 7: Recall @ 100 (precision @ 100) 7, with b 512.
Conclusion
In this paper, we develop SignRFF (sign random Fourier features) as an alternative to the popular method of SignRP (sign random projections). SignRFF and SignRP in the pipeline of embedding based retrieval (EBR) quite smoothly. EBR has become the standard industry practice. SignRFF can be applied after the embedding vectors have been trained to serve multiple purposes. It can be used as data reduction tool for efficiently storing embeddings and computing similarities. It can also be used an indexing scheme for approximate near neighbor (ANN) search, which is a crucial component in EBR. To assess the quality of SignRFF in the context of similarity rankings, a new unified theoretical framework to compare different hashing methods, based on a measure called Ranking Efficiency (RE). In terms of RE, we show that SignRFF outperforms SQ-RFF and KLSH which are existing methods related to RFF In the relatively high similarity region, RignRFF also outperforms SignRP in terms of the RE measure. The theoretical findings supported by experiments on datasets commonly used in the literature, Comparisons with deep learning as well as data-dependent hashing methods also provided, further confirm the effectiveness of SignRFF.
design
10

---

References
[1] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 253-262, Sydney, Australia, 2017.
[2] Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
[3] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. Min-wise independent permutations. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pages 327-336, Dallas, TX, 1998.
[4] Yue Cao, Mingsheng Long, Bin Liu, and Jianmin Wang. Deep cauchy hashing for hamming space retrieval. In Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1229-1237, Salt Lake City, UT, 2018.
[5] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (STOC), pages 380-388, Montreal, Canada, 2002.
[6] Beidi Chen, Zichang Liu, Binghui Peng. Zhaozhuo Xu, Jonathan Lingjie Li, Tri Dao, Zhao Song, Anshumali Shrivastava, and Christopher Ré. MONGOOSE: A learnable LSH framework for efficient neural network training. In Proceedings of the 9th International Conference on Learning Representations (ICLR), Virtual Event, Austria, 2021.
[7] Lin Chen, Hossein Esfandiari, Gang Fu, and Vahab S. Mirrokni. Locality-sensitive hashing for f-divergences: Mutual information loss and beyond. Advances Neural Information Processing Systems (NeurIPS), pages 10044-10555 Vancouver, Canada, 2019.
[8] Zhixiang Chen, Xin Yuan, Jiwen Lu, Qi Tian, and Jie Zhou, Deep hashing via discrepancy minimization. In Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition ( (CVPR), pages 6838-6847, Salt Lake City, UT, 2018.
[9] Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In Advances in Neural Information Processing Systems (NIPS), pages 1981-1989, Montreal, Canada, 2015.
[10] Shabnam Daghaghi, Tharun Medini, Nicholas Meisburger, Beidi Chen, Mengnan Zhao, and Anshumali Shrivastava. A tale of two efficient and informative negative sampling distributions. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 2319 2329, Virtual Event, 2021.
[11] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitive hashing scheme based p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG), pages 253-262, Brooklyn, NY, 2004.
[12] Thanh-Toan Do, Dang- Khoa Le Tan, Trung T. Pham, and Ngai-Man Cheung. Simultaneous feature aggregating and hashing for large-scale image search. In Proceedings of the 2017 IEEE Conference on Computer Vision and Puttern Recognition ( (CVPR), pages 4217-4226, Honolulu, HI, 2017.
[13] Wei Dong, Moses Charikar, and Kai Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 133- 2008
[14] Anne Driemel and Francesco Silvestri. Locality-sensitive hashing of curves. arXiv preprint arXiv: 004404 2017.
[15] Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li. MOBIUS: towards the next generation of query-ad matching in baidu's 's sponsored search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 2509-2517, Anchorage, AK, 2019.

---

[16] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maxi- mum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-11455 1995.
[17] Yunchao Gong and Svetlana Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 817-824, Colorado Springs, CO, 2011.
[18) Casper Hansen, Christian Hansen, Jakob Grue Simonsen, Stephen Alstrup, and Christina Lioma. Unsupervised semantic hashing with pairwise reconstruction. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval (SIGIR), pages 2009-2012, Virtual Event, China, 2020.
[19] Trevor J. Hastie, Robert Tibshirani, and Jerome H. Friedman. The elements of statistical learning: data mining, inference, and prediction. Springer, 2 edition, 2009.
[20] Kaiming He, Fang Wen, and Jian Sun. K-means hashing: An method for learning binary compact codes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2938-2945, 2013.
quantization
[21] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), pages 604 613, Dallas, TX, 1998.
[22] Sergey loffe. Improved consistent sampling, weighted minhash and L.1 sketching. In Pro- ceedings of the 10th IEEF International Conference on Data Mining (ICDM), pages 256-255, Sydney, Australia, 2010.
[23] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 131)):177-228 2011.
[24] Alexis Joly and Olivier Buisson. Random maximum margin hashing. Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 873-880, Colorado Springs, CO, 2011.
[25] Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
[26] Brian Kulis and Trevor Darrell. Learning to hash with binary reconstructive embeddings. In Advances in Neural Information Processing Systems (NIPS), pages 1042-1050, Vancouver, Canada, 2009.
[27] Brian Kulis and Kristen Grauman. Kernelized locality-sensitive hashing for scalable image search. In proceedings of the IEEE 12th International Conference on Computer Vision (ICCV), pages 2130-2137, Kyoto, Japan, 2009.
[28] Dung D. Le and Hady W. Lauw. Stochastically robust personalized ranking for LSH recommen- dation retrieval. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI), pages 4594-4601 New York, NY, 2020.
[29] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. comfexab/mnist// 1998.
[30] Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. Locality -ensitivee hashing scheme based on longest circular co-substring. In Proceedings of the 2020 International Conference on Management of Data (SIGMOD), pages OR, USA], 2020.
Online conference [Portland,
[31] Jinfeng Li, James Cheng, Fan Yang, Yuzhen Huang, Yunjian Zhao, Xiao Yan, and Ruihao Zhao. LoSHa: A general framework for scalable locality sensitive hashing. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 535-644, Shinjuku, Tokyo, Japan, 2017.
[32] Ping Li. Linearized GMM kernels and normalized random Fourier features. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 315-324, Halifax, Canada, 2017.
12

---

[33] Ping Li. Tunable GMM kernels. arXiv preprint
2017.
[34] Ping Li. Sign-full random projections. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pages 4205-4212, Honolulu, HI, 2019.
[35] Ping Li. Xiaoyun Li, and Cun-Hui Zhang. Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling. In Advances in Neural Information Processing Systems (NeurIPS), pages 15900-15910, Vancouver, Canada, 2019.
[36] Ping Li, Michael Mitzenmacher, and Anshumali Shrivastava. Coding for random projections. In Proceedings of the 31th 1tth International Conference Machine Learning (ICML., pages 676-684, Beijing, China, 2014.
[37] Ping Li, Gennady Samorodnitsky, and John E. Hopcroft. Sign cauchy projections and chi-square kernel. In Advances in Neural Information Processing Systems (NIPS), pages 2571 2571-2579, Lake Tahoe, NV, 2013.
[38] Shuyan Li, Zhixiang Chen, Jiwen Lu, Xiu Li, and Jie Zhou. Neighborhood preserving hashing for scalable video retrieval. In Proceedings of the 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 8211-8220, Scoul, Korea, 2019.
[39] Xiaoyun Li, Jie Gui, and Ping Li. Randomized kernel multi-view discriminant analysis. In Proceedings of the 24th European Conference on Artificial Intelligence (ECAI), pages 1276- I 1284, Santiago de Compostela, Spain, 2020.
[40] Xiaoyun Li and Ping Li. Generalization error analysis of quantized compressive learning, In Advances in Neural Information Processing Systems (NeurIPS), pages 15124-15134, Vancouver, Canada, 2019.
[41] Xiaoyun Li and Ping Li. Random projections with asymmetric quantization. In Advances in Neural Information Processing Systems (NeurIPS), pages 10857-10866, Vancouver, Canada, 2019.
[42] Xiaoyun Li and Ping Li. One-sketch-for-all: Non-linear random features from compressed linear measurements. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2647-2655, Virtual Event, 2021.
[43] Xiaoyun Li and Ping Li. Quantization algorithms for random Fourier features. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 6369-6380 Virtual Event, 2021.
[44] Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. Deep learning of binary hash codes for fast image retrieval. In Proceedings of the IEEE conference computer vision and pattern recognition workshops, pages 27-35, 2015.
[45] Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. Deep supervised hashing for fast image retrieval. In Proceedings of the 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 2064-2074 Las Vegas, NV, 2016.
[46] Hong Liu, Rongrong Ji, Yongjian Wu, Feiyue Huang, and Baochang Zhang. Cross-modality binary code learning via fusion similarity hashing. In Proceedings of the 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 6345-6353, Honolulu, HI, 2017.
[47] Song Liu, Shengsheng Qian, Yang Guan, Jiawei Zhan, and Long Ying. Joint-modal distribution- based similarity hashing for large-scale unsupervised deep cross-modal retrieval. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval (SIGIR). pages 1379-1388, Virtual Event, China, 2020.
[48] Mark Manasse, Frank McSherry, and Kunal Talwar. Consistent weighted sampling. Technical Report MSR-TR-2010072 Microsoft Research, 2010.
[49] Mohammad Norouzi, Ali Punjani, and David J. Fleet. Fast search in hamming space with multi-index hashing. In Proceedings of the 2012 IEFE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3108-3115, Providence, RI, 2012.
13

---

[50] Eng-Jon Ong and Miroslaw Bober. Improved hamming distance search using variable length hashing. In Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2000-2008, Las Vegas, NV, 2016.
[51] Lianyong Qi, Xuyun Zhang, Wanchun Dou, and Qiang Ni. A distributed locality-sensitive hashing-based approach for cloud service recommendation from multi-source data. IEEE J. Sel. Areas Commun., 35(11 (1:6:66666222,, 2017.
[52] Zexuan Qiu, Qinliang Su, Zijing Ou, Jianxing Yu, and Changyou Chen. Unsupervised hashing with contrastive information bottleneck. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (ICCAI, pages 959-965, Virtual Event / Montreal, Canada, 2021.
[53] Maxim Raginsky and Svetlana Lazebnik. Locality sensitive binary codes from thift-invariant kernels. In Advances in Neural Information Processing Systems (NIPS), pages 1509-1517, Vancouver, Canada, 2009.
[54] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NIPS), pages 1177-1184, Vancouver, Canada, 2007.
[55] Walter Rudin. Fourier Analysis on Groups. John Wiley & Sons, New York, NY, 1990.
[56] Dominik Schlegel and Giorgio Grisetti. HBST: A hamming distance embedding binary search tree for feature-based visual place recognition. IEEE Robotics Autom. Lett., 3(4):3741-3778, 2018.
[57] Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[58) Anshumali Shrivastava and Ping Li. Fast near neighbor search in high-dimensional binary data. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), Part I, pages 474 489, Bristol, UK, 2012.
[59] Anshumali Shrivastava and Ping Li. In defense of minhash over simhash. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS), pages 886-894, Reykjavik, Iceland, 2014.
[60] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proceedings of the 3rd International Conference on Learning Representa- tions (ICLR), San Diego, CA, 2015.
[61] Jingkuan Song, Tao He, Lianli Gao, Xing Xu, Alan Hanjalic, and Heng Tao Shen. Binary generative adversarial networks for image retrieval. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAAI), pages 394-444444 New Orleans, LA, 2018.
[62] Yitong Sun, Anna C. Gilbert, and Ambuj Tewari. But how does it work in theory? linear SVM with random features. In Advances in Neural Information Processing Systems (NeurIPS), pages 3383-3392, Montréal, Canada, 2018
[63] Danica J. Sutherland and Jeff G. Schneider. On the error of random Fourier features. In Proceedings of the Thirty-First Conference Uncertainty in Artificial Intelligence (UAI), pages 862-871, Amsterdam, The Netherlands, 2015.
[64] Anthony Tompkins and Fabio Ramos. Fourier feature approximations for periodic kernels in time-series modelling. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAA/), pages 4155 4162, New Orleans, LA, 2018.
[65] Yair Weiss, Antonio Torralba, and Robert Fergus. Spectral hashing. In Advances in Neural Information Processing Systems (NIPS), pages 1753-1760, Vancouver, Canada, 2008
[66] Zhaozhuo Xu, Beidi Chen, Chaojian Li, Weiyang Liu, Le Song, Yingyan Lin, and Anshumali Shrivastava. Locality sensitive teaching. Advances Neural Information Processing Systems (NeurIPS), pages 18049-18062, virtual, 2021.
14

---

[67] Zhaozhuo Xu, Zhao Song. and Anshumali Shrivastava. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. In Advances in Neural Information Processing Systems (NeurIPS), pages 5576-5589, virtual, 2021.
[68]
Chenggang Yan, Biao Gong, Yuxuan Wei, and Yue Gao. Deep multi-view enhancement hashing for image retrieval. IEEE Trans. Pattern Anal. Mach. Intell., 43(4):14445 1451, 2021.
[69] Erkun Yang, Tongliang Liu, Cheng Deng, Wei Liu, and Dacheng Tao. DistillHash: Unsupervised deep hashing by distilling data pairs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 2946-2955, Long Beach, CA, 2019.
[70] Erkun Yang, Tongliang Liu, Cheng Deng, and Dacheng Tao. Adversarial examples for hamming space search. IEEE Trans. Cybern., 50(4): 2020.
[71] Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nyström method vs random fourier features: A theoretical and empirical comparison. In Advances in Neural Information Processing Systems (NIPS), pages 685,493, Lake Tahoe, NV, 2012.
[72] Tan Yu, Jingjing Meng, and Junsong Yuan. Multi-view harmonized bilinear network for 3D object recognition. In Proceedings of the 2018 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pages 186-194, Salt Lake City, UT8, 2018.
[73] Amir Zandieh, Navid Nouri, Ameya Velingker, Michael Kapralov, and Ilya P. Razenshteyn. Scaling up kernel ridge regression via locality sensitive hashing. In Proceedings of th 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 4088-4097, Online [Palermo, Sicily, Italy], 2020.
[74] Jian Zhang, Avner May, Tri Dao, and Christopher Ré. Low- Low-precision random Fourier features for memory-constrained kernel approximation. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1264-1274 Naha, Okinawa, Japan, 2019.
[75] Weijie Zhao, Shulong Tan, and Ping Li. SONG: approximate nearest neighbor search GPU. In Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE), pages 1033-1044, Dallas, TX, 2020.
[76] Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. Möbius transformation for fast inner product search on graph. In Advances in Neural Information Processing Systems (NeurIPS), pages 8216-8227, Vancouver, Canada, 2019.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results? [Yes] Public datasets.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] All results are averaged over 5 runs.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Our experiments are performed on single core 2.0GHz CPU.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "mJRxs8J3zjN", "reviewer": "Reviewer_HPJi", "summary": "This paper modified the LSH method on RFF feature in [35] by removing the random noise and prove that it is still a LSH. Moreover, this paper also provides a new metric ranking efficiency to evaluate hash codes. Experiments are conducted on multiple data sets like SIFT, CIFAR, MNIST, comparing the proposed method to original one in [35] as well as other unsupervised hashing methods and one deep hashing method. ", "questions": "--A more rigorous analysis about why $V_{xy}$ can be discarded.\n--Compared to more SOTA unsupervised deep hashing methods.\n--Evaluate the codes with multi hash tables besides hamming ranking.", "limitations": "I did not find the discussion of the technical limitation or potential negative societal impact, even though the authors claims they are discussed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n--The theoretical part of the proposed modification looks sound.\n\n--The experiments show the proposed modification outperforms the original one in [35].\n\nWeaknesses:\n\n--To prove the proposed SignRFF is LSH, the major technical difficulty (and hence contribution) is to formulate $f(z_x, z_y | \\rho)$ and prove  it is increasing with $\\rho$, which, however, is borrowed from [26]. So the technical contribution is not high.\n\n--To get the ranking efficiency metric, $V_{xy}$ is discarded from equation (10). However, is it reasonable?  Is $V_{xy}$ close to 0, or very small, compared to $V_{x}$ and $V_{y}$, at least under some conditions? It is  is not rigorous to discard the term simply because it is hard to derive.\n\n--There are many unsupervised deep hashing methods, and only one of them is compared.\n\n--Only hamming ranking with long codes is used to evaluate the hash codes in this paper. However, the real practical way to use hash codes is actually constructing multi hash tables, each with a short code, which is how the sub-linear performance of LSH can be achieved, (and also how the complexity bound is proved).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PWYNqSoo10a", "reviewer": "Reviewer_vbLr", "summary": "The authors propose an RFF-based binary coding method that drops the additional perturbation term from the previously popular stochastic quantization RFF method. They not only demonstrate improved performance on retrieval tasks but also prove locality-sensitivity for their proposed method. ", "questions": "In all the cases, the KLSH performs better than SQ-RFF but never outperforms Sign-RFF. Could you elaborate more on why that is happening? What exactly is making SQ-RFF lag behind KLSH, and how sign-RFF is able to overcome that?", "limitations": "n/a", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed algorithm is simple yet powerful with empirical success on the retrieval task.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A3KtgXH1Rfx", "reviewer": "Reviewer_U4Yu", "summary": "The paper investigated the quality of LSH binary coding for efficient nearest neighbor retrieval. They proposed a simple strategy to extract binary codes from Random Fourier Feature (RFF) and designed a new measure called ranking efficiency to evaluate the binary coding performance of different LSH methods. Extensive experiments validated the effectiveness and consistency of ranking efficiency from theoretical evaluation and the superiority of SignRFF with sufficient binary codes.\n", "questions": "Q1. Followed by W1, as they have the formulas of collision probability for SQ-RFF and Sign-RFF (Equations 6 and 8), can they provide more empirical results (or theoretical analysis) about the variance reduction?\n\nQ2. Followed by W2, can they follow the same settings of Figure 1 and plot the curves of $V_{xy}$ compared with $(V_x + V_y) / 2$?\n", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nS1. The authors simplify the binary coding based on RFF, and they demonstrate the new SignRFF is still locality-sensitive. \n\nS2. The new measure of ranking efficiency is very interesting to me, especially its consistency in both theory and practice. As the LSH efficiency (called by the authors) mainly targets the efficiency and space overhead of LSH schemes, it seems to be a good complement measure of accuracy.\n\nS3. The experimental results are comprehensive and convincing. \n\nS4. This paper is well written and easy to follow.\n\nWeaknesses\n\nW1.I have a minor concern about the contributions of this paper, especially on the part of SignRFF. As the demonstration of the locality-sensitive property of SignRFF primarily comes from Lemma 1 [26], this part might be more solid if they could make an empirical analysis (or theoretical analysis if possible, will be better) of the variance reduction by removing the noise $\\xi$. \n\nW2. Even though the ranking efficiency (RE) is very interesting to me, the operation to directly removing the covariance $V_{xy}$ is less promising. It will be more convincing to me if they could conduct experiments to validate that the values of $V_{xy}$ for most cases of $\\rho$ and $c$ are much small than the values $(V_x + V_y) / 2$. \n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "8XE9BFPDwm4", "reviewer": "Reviewer_bnZk", "summary": "This paper studies the problem of binary code constructions, which can be used to approximate the original high-dimensional vectors of real numbers. The approximation can save storage space and accelerate similarity search runtime. The paper introduces a new method, called SignRFF and claims the following contributions: (1) better performance than extensive baselines (i.e. LSH, ITQ, SpecH, BRE, SQ-RFF, and KLSH) (2) introduces a new metric called ranking efficiency to evaluate the quality of binary codes.      ", "questions": "Address the weaknesses", "limitations": "N.A.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nS1: Novel technical contribution. The paper targets at SQ-RFF algorithm, which is becoming a standard for binary code construction and has over 750 citations since 2010. The paper reveals that the random noise component of the SQ-RFF algorithm is unnecessary, and it proposes a new algorithm SignRFF to remove the component. Experiments verify that SignRFF is more effective than SQ-RFF. \n\nS2: Solid experiments. The paper compares SignRFF with not only SQ-RFF but also a set of other strong baselines, including LSH, ITQ, SpecH, BRE, SQ-RFF. These baselines have broad impact in the field. For example, both LSH and ITQ have gained more than 1000 citations since the works were published.  \n\nWeaknesses:\n\nW1: Unclear motivation about new metric. The paper introduces a new metric called ranking efficiency to evaluate the quality of binary codes. The new metric is a key contribution claimed by the authors. It is unclear why we need a new metric. There are already a set of metrics commonly used in the field, including recall@#bits or recall@topk. It will be convincing if the paper explains the motivation and how the new metric differs from common ones.\n  \nW2: no deep hashing methods in key experiments. Figures 3 and 4 show that the proposed method outperforms a number of baselines. But none of the baselines is deep learning based. The paper moves comparison with deep hashing (i.e. CIB) to Figure 5, where the metric differs from Figures 3 and 4. It will be more convincing if the papers can add the performance numbers of CIB to Figures 3 and 4.   \n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept