Year: 2021

Abstract:
The method of Random Fourier Feature (RFF) has been popular for large-scale learning, which generates non-linear random features of the data. It has also been used to construct binary codes via stochastic quantization for efficient information retrieval. In this paper, we revisit binary hashing from RFF, and propose SignRFF, a new and simple strategy to extract RFF-based binary codes. We show the locality-sensitivity of SignRFF, and propose a new measure called ranking efficiency to theoretically compare different Locality-Sensitive Hashing (LSH) methods, which provides a new systematic and unified framework for LSH comparison. It suggests that SignRFF should be preferred in the high similarity region. Experiments are conducted to show that SignRFF is consistently better than the previous RFF-based method, and also outperforms other data-dependent and deep learning based hashing methods with sufficient number of hash bits. Moreover, the proposed ranking efficiency aligns well with the empirical search performance.

heading: 1 INTRODUCTION
text: Developing efficient machine learning algorithms in large-scale problems has been an important research topic to deal with massive data. In this paper, we focus on efficient retrieval/search methods, specifically, by designing similarity-preserving binary representations of the data. That is, for each data vector x ∈ Rd, we hash it into a length-b binary 0/1 vector h(x) ∈ {0, 1}b, 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 (Weiss et al., 2008; Gong & Lazebnik, 2011; Kulis & Darrell, 2009; He et al., 2013; Lin et al., 2015; Liu et al., 2016; 2017; Song et al., 2018; Yu et al., 2018; Yan et al., 2021). The benefits are two-fold. Firstly, it may largely reduce the memory cost for storing massive datasets, especially with high-dimensional data. Secondly, it can significantly speedup the retrieval process. For instance, the binary codes can be used to build hash tables (e.g., Indyk & Motwani (1998)) for sub-linear time approximate nearest neighbor (ANN) search. Moreover, in the Hamming space, we can also apply exhaustive search, which is much faster than computing the Euclidean distances, plus the technique of multi-index hashing (Norouzi et al., 2012) can further accelerate the exact Hamming search by orders of magnitude.
In general, binary hashing methods can be categorized into supervised and unsupervised approaches. In this work, we focus on the unsupervised setting. Locality-Sensitive Hashing (LSH) (Indyk & Motwani, 1998) is one of the early hashing methods leading to binary embedding. The LSH targeting at cosine similarity (Charikar, 2002), also known as SimHash, generates binary hash codes using random hyperplanes by taking the sign of data-independent random Gaussian projections. For the cosine similarity, LSH has strict theoretical guarantee on the approximation error and search efficiency, but typically requires relatively long codes to achieve good performance. Hence, many works have focused on learning data-dependent short binary hash codes, through different objective functions. Examples include Iterative Quantization (ITQ) (Gong & Lazebnik, 2011), Spectral Hashing (SpecH) (Weiss et al., 2008) and Binary Reconstruction Embedding (BRE) (Kulis & Darrell, 2009). Recently, some unsupervised deep learning based methods have been proposed in the computer vision community, many of which are, to some extent, “task-specific” for cross-modal/video/image retrieval, implemented based on some deep models like the autoencoder and VGG-16 (Liu et al., 2016; Do et al., 2017; Chen et al., 2018; Li et al., 2019; Yang et al., 2019; Hansen et al., 2020; Liu et al., 2020; Qiu et al., 2021). By taking the advantage of the complicated model structures (e.g., CNN layers), these deep methods show promising performance in many image retrieval tasks.
Compared with the data-dependent methods (including deep methods), LSH has three advantages:
• Although the data-dependent procedures can provide improved performance with fewer binary codes, a known undesirable effect of many of these mechanisms is the performance degradation when we increase the code length b, as reported in prior literature (Raginsky & Lazebnik, 2009; Joly & Buisson, 2011). In our experiments, we will show that this may also be an issue for deep learning based methods. On the other hand, the performance (i.e., search accuracy) of the data-independent LSH would keep boosting with larger b. In many scenarios, it is often the case that only using short codes (e.g., ≤ 128 bits) cannot achieve a desirable level of search accuracy for practical purposes. In these cases, one may need to use longer codes anyway, where LSH could be more favorable.
• LSH is very simple to implement (only with random projections), while data-dependent methods require additional optimization/training which might be costly. Moreover, large deep learning models would typically need longer inference time, which might be infeasible in practice where the query speed is important.
• It is difficult to characterize the properties of the data-dependent methods theoretically, while LSH enjoys rigorous guarantees on the retrieval/approximation performance.
Therefore, LSH is still a popular hashing method with great research interest and many practical applications (Shrivastava & Li, 2014; Qi et al., 2017; Driemel & Silvestri, 2017; Chen et al., 2019; Zandieh et al., 2020; Lei et al., 2020; Daghaghi et al., 2021).

heading: 1.1 LOCALITY-SENSITIVE HASHING FROM RANDOM FOURIER FEATURES
text: Kernel methods have gained great success in many machine learning tasks (Schölkopf & Smola, 2002; Zhu & Hastie, 2001; Avron et al., 2017; Sun et al., 2018). However, standard kernel methods require the n × n kernel matrix, which becomes computationally expensive on large-scale datasets with massive data points. To this end, Rahimi & Recht (2007) proposes the method of random Fourier feature (RFF), which defines a feature map that approximates shift-invariant kernels by the linear inner products. As such, the RFF preserves the “non-linear locality structure” of the data. This leads to numerous applications in large-scale learning where one trains linear models on RFF to approximate training non-linear kernel machines (Yang et al., 2012; Chwialkowski et al., 2015; Sutherland & Schneider, 2015; Avron et al., 2017; Sun et al., 2018; Tompkins & Ramos, 2018).
Given the popularity of RFF, one natural step is to apply it to search problems. Raginsky & Lazebnik (2009) proposes to construct binary codes from the RFF using stochastic binary quantization. We call this method “SQ-RFF”, whose convergence (as b→∞) and concentration can be theoretically characterized. The author showed that SQ-RFF can achieve competitive search accuracy with sufficient b, e.g., b ≥ 512. Since RFF itself is a widely used tool for large-scale kernel learning, SQ-RFF could be a convenient/useful tool in practical scenarios where RFF has been generated for training kernel machines, and the data scientist wants to further use it for efficient near neighbor retrieval.

heading: 1.2 OUR CONTRIBUTIONS
text: Given the benefits of LSH and RFF, we revisit hashing methods for non-linear kernels, and improve the prior RFF based hashing method. Our approach is named as “SignRFF”. Specifically,
• We theoretically compare several linear and non-linear LSH methods in terms of a novel measure called the ranking efficiency, which is defined based on the probability of retrieving a wrong/reversed similarity ranking. Under this unified metric, the proposed SignRFF is uniformly better than SQ-RFF. Moreover, the ranking efficiency also indicates that typically one should prefer SignRFF over linear LSH when the near neighbors are close to each other, which is the first systematic comparison of linear vs. non-linear LSH in literature.
• Empirically, we conduct near neighbor search experiments on benchmark image datasets to compare the proposed SignRFF with other popular hashing methods, which verifies the superiority of SignRFF over SQ-RFF. We validate that the ranking efficiency metric aligns well with the empirical results. Moreover, SignRFF outperforms various competing methods (including deep methods) with moderately large number of hash bits, indicating its advantage in applications to achieve a high search recall/precision.

heading: 2 PRELIMINARIES

heading: 2.1 LOCALITY-SENSITIVE HASHING (LSH)
text: In large-scale information retrieval, exhaustive search of the exact nearest neighbors is usually too expensive. A common relaxation in this setting is the Approximate Nearest Neighbor (ANN) search, where we return the “good” neighbors of a query with high probability. In this paper, we will consider the search problem with data points in Rd. X denotes the database consisting of n data points, and q is a query point. x,y are two data points with ρ = cos(x,y).
Definition 2.1 (S̃-neighbor). For a similarity measure S : Rd × Rd 7→ R, the S̃-neighbor set of q is defined as {x ∈X : S(x, q) > S̃}. Definition 2.2 ((c, S̃)-ANN). Assume δ > 0 is a parameter. An algorithm A is a (c, S̃)-ANN method provided the following: with probability at least 1− δ, for 0 < c < 1, if there exists an S̃-neighbor of q in X , A returns a cS̃-neighbor of q.
One popular method satisfying Definition 2.2 is the Locality-Sensitive Hashing (LSH).
Definition 2.3 (Indyk & Motwani (1998)). A family of hash functions H is called (S̃, cS̃, p1, p2)locality-sensitive for similarity measure S and 0 < c < 1, if for ∀x,y ∈ Rd and hash function h uniformly chosen from H, it holds that: 1) If S(x,y) ≥ S̃, then P (h(x) = h(y)) ≥ p1; 2) If S(x,y) ≤ cS̃, then P (h(x) = h(y)) ≤ p2, with p2 < p1.
A key intuition of LSH is that, similar data points with have higher chance of hash collision in the Hamming space. In this paper, we will specifically consider the LSH for the cosine similarity (Charikar, 2002). For a data vector x ∈ Rd, the LSH binary code is given by
LSH: hLSH(x) = sign(wTx), (1)
where wT is a standard Gaussian random vector. We use b i.i.d. w1, ...,wb to generate b LSH binary codes. The collision probability between the codes of two data points x,y is
P (hLSH(x) = hLSH(y)) = 1− cos−1(ρ)
π , (2)
where ρ = cos(x,y) is their cosine similarity. Note that P (hLSH(x) = hLSH(y)) is increasing in ρ, which, By Definition 2.3, is the key to ensure the locality sensitivity.

heading: 2.2 KERNELIZED LOCALITY-SENSITIVE HASHING (KLSH)
text: In this paper, we will consider the popular Gaussian kernel function defined for x,y ∈ Rd as
k(x,y) = exp
( −γ2‖x− y‖2
2
) ,
where γ is a hyper-parameter. Let Ψ : Rd 7→ F be the feature map with the kernel induced feature spaceF . To incorporate non-linearity in LSH, Kulis & Grauman (2009) proposes Kernelized Locality-Sensitive Hashing (KLSH), by applying LSH (1) in the kernel induced feature space F , i.e., h(x) = sign(wTΨ(x)). However, as in many cases (e.g., for the Gaussian kernel) the map Ψ cannot be explicitly identified, constructing the random Gaussian projection vector w needs some careful design. KLSH approximates the random Gaussian distribution using a sufficient number of data points, by the Central Limit Theorem (CLT) in the Reproducing Kernel Hilbert Space. One first samples m data points from X to form a kernel matrix K, then uniformly picks t points from [1, ...,m] at random to approximate the Gaussian distribution. The hash code has the form
KLSH: hKLSH(x) = sign( m∑ i=1 w(i)k(x,xi)), (3)
where w = K−1/2et, and et ∈ {0, 1}m has ones in the entries with indices of the t selected points. We see that the codes h1, ..., hb are actually dependent, and the quality of using CLT to approximate Gaussian distribution is not guaranteed, especially in high-dimensional kernel feature space. Jiang et al. (2015) re-formulates KLSH as applying LSH on the kernel principle components
in the kernel induced feature space, resolving a theoretical concern of KLSH. Notably, since KLSH uses a pool of data samples to approximate the Gaussian distribution, the hash codes are in fact dependent in practical implementation. It is observed that the performance of KLSH also drops as b increases (Joly & Buisson, 2011), similar to the behavior of many data-dependent methods. We provide more detailed explanation in Appendix C.

heading: 3 LOCALITY-SENSITIVE BINARY CODES FROM RANDOM FEATURES
text: Rahimi & Recht (2007) proposes random Fourier feature (RFF) to alleviate the computational bottleneck of standard kernel methods. For a data vector x, the RFF for the Gaussian kernel is defined as
RFF: F (x) = cos(wTx + τ), (4) where w ∼ N(0, γ2Id) and τ ∼ Unif(0, 2π) where Id is the identity matrix. It holds that
E[F (x)F (y)] = k(x,y)/2. That is, the non-linear kernel similarity can be preserved in expectation by the linear inner product of RFF. To obtain good approximation, we generate b independent RFFs for each data point using i.i.d. w1, ...,wb and τ1, ..., τb, which can be subsequently used for various learning tasks.
From now on, we will assume the data vectors are normalized to have unit l2 norm: 1) this is a standard pre-processing step in practice; and 2) the theoretical guarantees of LSH (1) is only valid for the cosine similarity (i.e., normalized data). Nevertheless, our analysis can be easily extended to the general unnormalized case. With normalized data, the Gaussian kernel can be written as a function of ρ = cos(x,y):
k(ρ) ≡ k(x,y) = e−γ 2(1−ρ).
To extend RFF to efficient search problems, Raginsky & Lazebnik (2009) designs a mapping [0, 1] 7→ {0, 1} for each RFF. For x ∈ Rd, the code is produced by stochastic quantization (SQ):
hSQ(x) = sign(F (x) + ξ) = sign(cos(w Tx + τ) + ξ), (5)
where ξ is a random perturbation from Unif(−1, 1), with two possible choices on the dependency. In Raginsky & Lazebnik (2009), the same ξ is used for all data points. Another option in literature is to use i.i.d. ξ for each data point, such that the binary codes admit E[h(x)h(y)] = k(x, y). For example, it is used in Zhang et al. (2019); Li & Li (2021) for large-scale low-precision training. We also tested this strategy in our experiments. The search performance is however very poor, because more variation is introduced. On the other hand, we actually do not need the exactly estimation/recovery of the kernel values in search problems. Hence, in this paper we will consider the baseline using the same ξ for all data samples as in Raginsky & Lazebnik (2009). The collision probability of the so-called “SQ-RFF” is given as follows. Theorem 3.1 (Raginsky & Lazebnik (2009)). For the SQ-RFF (5), for ∀x,y ∈ Rd, it holds that
PSQ(ρ) := P (hSQ(x) = hSQ(y)) = 1− 8
π2 ∞∑ s=1 1− e−γ2s2(1−ρ) 4s2 − 1 . (6)
This method is locality-sensitive w.r.t. ρ because of the fact that (6) is an increasing function of ρ. Hence, it is also locality-sensitive w.r.t. the kernel k(ρ) by the monotonicity of k(ρ).
Proposition 3.2. The SQ-RFF (5) is (k̃, ck̃, PSQ(ρ1), PSQ(ρ2))-locality sensitive w.r.t. similarity measure k(·), where ρ1 = log(k̃)/γ2 + 1 and ρ2 = log(ck̃)/γ2 + 1.
In the kernel approximation problem, stochastic rounding introduces higher variance due to the noise ξ, which hurts the kernel estimation accuracy (Li & Li, 2021). Later, we will see that a similar effect also presents in search problems. To this end, we propose our simple strategy—directly taking the sign of the RFF, i.e., applying deterministic quantization. Formally, the so-called “SignRFF” approach constructs the binary codes for x by
SignRFF: hsign(x) = sign(F (x)) = sign(cos(wTx + τ)). (7) Operationally, SignRFF is extremely convenient. At the first glance, it may appear a bit surprising that this simple scheme has not been studied in literature. We believe one of the reasons is that the theoretical correctness of SignRFF is hard to justify. Indeed, with some recent progress on RFF, we can show that SignRFF is locality-sensitive.
Lemma 3.3 (Li & Li (2021)). For two normalized data points x,y with cosine ρ, let F (·) be the RFF defined as (4). The joint distribution of zx = F (x) and zy = F (y) is
f(zx, zy|ρ) =
∞∑ k=−∞ [ φσ(a ∗ x − a∗y + 2kπ) + φσ(a∗x + a∗y + 2kπ) ] π √ 1− z2x √ 1− z2y , (8)
where a∗x = cos −1(zx), a ∗ y = cos −1(zy), and φσ(·) is the p.d.f. of N(0, σ2) with σ = √
2(1− ρ)γ. Furthermore, E[sign(F (x))sign(F (y))] is an increasing function of ρ. Proposition 3.4. The SignRFF (7) is (k̃, ck̃, Psign(ρ1), Psign(ρ2))-locality sensitive w.r.t. to k(·), with ρ1 = log(k̃)/γ2 + 1 and ρ2 = log(ck̃)/γ2 + 1, with collision probability
Psign(ρ) := P (hsign(x) = hsign(y)) = 2 ∫ 1 0 ∫ 1 0 f(zx, zy|ρ)dzxdzy, (9)
where f(zx, zy|ρ) is the density function (8).
Proof. By Definition 2.3 and the monotonicity of k(ρ), it suffices to show that the collision probability, Psign(ρ), is increasing in ρ. This immediately follows from Lemma 3.3 that E[sign(F (x))sign(F (y))] = Psign(ρ)− (1− Psign(ρ)) = 2Psign(ρ)− 1 is increasing in ρ.

heading: 4 THEORETICAL COMPARISON OF LSH METHODS: A NEW SCHEME
text: In our theoretical analysis, we assume for KLSH (Kulis & Grauman, 2009) that the Gaussian projection in the kernel induced feature space F is truly random. That is, KLSH “ideally” performs LSH in the kernel space: hKLSH(x) = sign(wTΨ(x)) where w is a random Gaussian vector with proper dimensionality. Since Ψ(x)TΨ(y) = k(x,y), applying (2) in F we obtain
PKLSH(ρ) := P (hKLSH(x) = hKLSH(y)) = 1− cos−1(e−γ 2(1−ρ))
π . (10)
Proposition 4.1. KLSH is (k̃, ck̃, 1− cos −1(k̃) π , 1− cos−1(ck̃) π )-locality sensitive w.r.t. k(·).
Recall Definition 2.3 of the (k̃, ck̃, p1, p2)-LSH. It is known (Indyk & Motwani, 1998) that one can construct an LSH data structure with the worst case query time O(nR), where R := log p1log p2 is called the LSH efficiency, which has been used in literature to theoretically compare different LSH methods, e.g. SimHash vs. MinHash (Shrivastava & Li, 2014). However, we should note that the LSH efficiency is only based on a worst case analytical bound. Therefore, it may not well explain or predict the practical search performance (See Appendix A.1 for related results).
We propose a novel measure for evaluating the search accuracy of LSH schemes, namely, the ranking efficiency, that can better compare LSHs in practice. The definition is motivated by the observation that regardless of the concrete approach (e.g., building hash tables or exhaustive search), the nearest neighbor retrieval, to a large extent, essentially boils down to estimating the Euclidean (cosine) similarity rankings in the Hamming space. Suppose x and y are two points in the database, and q is a query with ρx = cos(q,x), ρy = cos(q,y). Assume x is the true nearest neighbor of q, implying ρx > ρy . By the property of LSH, we know that the hash collision probability px > py . For an LSH hash function h, define the corresponding collision probability estimators as
p̂x = 1
b b∑ i=1 1{hi(x) = hi(q)}, p̂y = 1 b b∑ i=1 1{hi(y) = hi(q)}. (11)
Now the problem becomes comparing p̂x and p̂y to estimate the true ranking of px and py . We consider the event of obtaining a wrong similarity comparison from our estimation, i.e. p̂x ≤ p̂y . Obviously, a higher probability implies worse search accuracy, as we are more likely to retrieve the wrong nearest neighbor y. Denote
Ex = E[1{h(x) = h(q)}], Ey = E[1{h(y) = h(q)}], Cov(1{h(x) = h(q)},1{h(y) = h(q)}) = Σ = ( Vx Vxy Vxy Vy ) .
By the CLT, we know that as b → ∞, ( p̂x p̂y ) ∼ N( ( Ex Ey ) ,Σ/b). This approximation would be good with a sufficiently large number of b, e.g., b ≥ 30. In this regime, we can compute
P (p̂x ≤ p̂y) = P (p̂x − p̂y ≤ 0) = 1− Φ
( √ b(Ex − Ey)√
Vx + Vy − 2Vxy
) , (12)
where Φ(·) is the c.d.f. of standard normal distribution. For all the LSH methods studied in this paper, theEx andEy are simply the collision probabilities, and Vx = Ex(1−Ex), Vy = Ey(1−Ey) from the binomial distribution. Yet, the covariance Vxy is difficult to be analytically computed. For simplicity, we assume that this term has same relative influence on the estimators of all approaches, thus dropping it in the formal definition of the ranking efficiency, which is given as below. Definition 4.1 ((ρ, c)-Ranking Efficiency). For a LSH method, let the hash collision probability at cosine ρ and cρ beE andEc, respectively. Let V = E(1−E), Vc = Ec(1−Ec). The (ρ, c)-ranking efficiency is defined as RE = E−Ec√
V+Vc .
Remark 4.1. The RE can also be defined in terms of the non-linear kernel k(·). We use cosine ρ here to address both linear and non-linear LSH for generality. In most retrieval applications, we may concern more about high c (e.g., c = 0.95) which corresponds to similar data points.
In general, higher RE implies smaller probability of the reversed estimated ranking in (12), which is more favorable. In Figure 1, we provide the comparison of ranking efficiency at different ρ, which covers the cases in our empirical study (Section 5). We observe some consistent patterns:
• Non-linear LSH. Firstly, compared with the other RFF-based approach SQ-RFF, the proposed SignRFF is uniformly more efficient at all ρ. In other words, in search tasks, the stochastic quantization of SQ-RFF introduces more “variation” that lowers the ranking efficiency. Compared with KLSH, SignRFF is more efficient when γ is large (e.g., γ > 2) in all plots, while KLSH tends to be more efficient with small γ. In general, SignRFF is the best in terms of ranking efficiency.
• When should we prefer non-linear LSH? The ranking efficiency gives a novel theoretical guidance on the appropriate choice between linear and non-linear LSH methods. We see that, when the target ρ is high (e.g., ρ > 0.8), with proper tuning, kernel methods (SignRFF and KLSH) can be more efficient than linear LSH. However, if the target ρ is small (e.g., ρ < 0.7), linear LSH might be more favorable. In other words, SignRFF could be better than LSH on datasets where the near neighbors are close to each other with high similarity/short distance, which is usually the case for, e.g., image data.
The ranking efficiency measures the search accuracy for given target ρ value. In practice, a dataset contains many different pairs (with different ρ). Our experiments on real datasets in the next section show that the performance is largely consistent with the prediction based on the “average ρ” value.

heading: 5 EXPERIMENTS
text: In this section, we conduct image retrieval experiments on benchmark datasets to demonstrate the effectiveness of our approach and justify the theoretical comparison of ranking efficiency.
5.1 DATASETS, METHODS AND EVALUATION
Datasets. We use three popular benchmark datasets in image retrieval literature. The SIFT1M dataset (Jégou et al., 2011) contains 1M 128-dimensional SIFT image features, and 1000 query samples. The MNIST dataset (LeCun, 1998) contains 60000 hand-written digits. We randomly choose 1000 samples from the test set as the query points. The CIFAR dataset (Krizhevsky, 2009) contains 50000 natural images. We use the gray-scale images in our experiments, and randomly select 1000 test samples as the queries. In addition, when comparing our methods with VGG-16 (Simonyan & Zisserman, 2015) based deep methods, following prior literature (e.g.,Yang et al. (2019); Qiu et al. (2021)), we use the 4096-d features from the last fully connected layer of the pre-trained
VGG-16 network as the input data for shallow methods for fairness. This dataset is called “CIFARVGG”. On all datasets, the data points are normalized to have unit norm. In Figure 2, we report the average cosine similarity between queries to their N -nearest neighbor, from N = 1 to 1000.
Methods. We compare the following unsupervised hashing methods: 1) LSH (Charikar, 2002); 2) Iterative Qauntization (ITQ) (Gong & Lazebnik, 2011); 3) Spectral Hashing (SpecH) (Weiss et al., 2008); 4) Binary Reconstruction Embedding (BRE) with 1000 random samples for model training as suggested by Kulis & Darrell (2009); 5) KLSH with m = 500 random samples for formulating the kernel matrix and t = 50 samples for the CLT Gaussian approximation, which should be more accurate than (300, 30) as recommended in Kulis & Grauman (2009); 6) SQ-RFF (Raginsky & Lazebnik, 2009); 7) Our proposed SignRFF. For kernel LSH methods 5) - 7), we tune the parameter γ over 0.1 ∼ 5 and report the best γ with highest average recall over multiple b = 32 ∼ 1024. For each tested method, we generate binary codes and perform exhaustive search in the Hamming space.
Evaluation. For each query point, the ground truth nearest neighbors are set by ranking the topN = 100 smallest Euclidean distance (top-100 largest cosine similarity). After running each algorithm, the Hamming ranking returns R estimated nearest neighbors to each query. We report the average recall over 1000 queries. Note that, recall@N is equivalent to precision@N in our setting. See Appendix A.2 for more detailed explanation and additional results on the retrieval precision.

heading: 5.2 RESULTS
text: In Figure 3, we report the recall@N (precision@N) against the number of binary codes b:
• On SIFT and MNIST, data-dependent methods (ITQ, SpecH, BRE) perform well with low bits, but the recall does not improve much after b > 100 ∼ 200. Yet, this low bit region does not help much in practice, since the recall level is too low (e.g. < 0.3 on SIFT and CIFAR) to be satisfactory for real-world tasks. As we mentioned, this is a known limitation of these methods. When b ≥ 256, LSH-type methods start to dominate, as expected. On CIFAR, SignRFF and KLSH outperform 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 SignRFF 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.
In Figure 4, we present the recall versus the number of retrieved neighbors, with b = 512 and b = 1024. SignRFF performs the best among all competing methods on SIFT and CIFAR. On MNIST, SignRFF performs similarly to LSH and better than the other methods with sufficient b.
Ranking efficiency. In Figure 5, we additionally provide the recall against the Gaussian parameter γ, to justify the effect of ranking efficiency discussed in Section 4. In Figure 1, the theoretical comparison suggests that KLSH would perform better with small γ, while SignRFF is more efficient larger γ, which matches the empirical evidence (e.g., 1 vs. 2.5 on SIFT). Moreover, as shown in Figure 2, the average ρ between each query and its neighbors is around 0.8, 0.9 and 0.95 for MNIST, SIFT and CIFAR, respectively. Figure 1 predicts that compared with SQ-RFF (blue), LSH (green) would perform better on MNIST, similarly on SIFT, and worse on CIFAR, which aligns with
Figure 3 and Figure 4. Therefore, although the behavior of KLSH slightly deviates from the theory due to the dependence among hash codes, our experiments in general verify the effectiveness of the ranking efficiency as an informative measure to compare different LSH methods.

heading: 5.3 COMPARISON WITH DEEP HASHING
text: We provide additional experiments on the CIFAR-VGG dataset with a recent unsupervised deep hashing method for image retrieval, the Contrastive Information Bottleneck (CIB) (Qiu et al., 2021), which uses VGG-16 pre-trained model as the backbone. We apply the same training setting as in Qiu et al. (2021): 60 epochs, 64 mini-batch size and Adam optimizer with 0.001 learning rate. We note that, CIB (as well as many other deep methods) is not designed to find the most similar data points. Instead, by using techniques like cropping and rotation in training CNN, these methods aim at robustly finding data points with same label as the query, which does not necessarily imply high similarity with the query when represented by the fc7 layer of VGG-16. Hence, to favor CIB, in this experiment we expand the range of true neighbors of a query to the top-1000 similar points in the database. See Appendix B for examples of the retrieved images and more discussion.
• From Figure 6, we see that CIB performs the best with 32 and 64 bits than LSH methods, which illustrates the benefit of deep hashing with short codes. However, the recall is only 0.3∼0.4, and does not improve with more bits, since simply increasing the size of last layer in the deep net typically would not elevate the model performance significantly. When b ≥ 256, LSH, SignRFF and KLSH provide much higher recall than CIB.
• Among LSHs, KLSH performs the best on this task. SignRFF again consistently improves SQ-RFF, and matches the recall of KLSH with b = 1024. In addition, linear LSH slightly outperforms SignRFF, which is consistent with the theoretical comparison in Figure 1 as expected (the target ρ is ∼0.7 for this task, where LSH is more efficient than SignRFF).

heading: 6 CONCLUSION
text: Random Fourier Feature (RFF) is a popular method in large-scale kernel learning, which has also been used for constructing binary codes for fast non-linear neighbor search (Raginsky & Lazebnik, 2009). In this work, we revisit RFF-based binary hashing, and propose a new strategy named SignRFF. We analyze its locality-sensitive property, and provide a new unified theoretical framework to compare different LSH methods, based on a measure called ranking efficiency. The metric implies that, we should prefer SignRFF over the linear LSH in the high similarity region when data points are close to each other. Empirically, we demonstrate that SignRFF is significantly better than the previous RFF-based approach, SQ-RFF, and outperforms data-dependent and deep hashing methods when the number of hash bits is moderately large. Moreover, the theoretical comparisons of the proposed ranking efficiency is consistent with the empirical results, suggesting that it could serve as a good theoretical tool for comparing the search performance of different LSH methods in practice.

heading: A MORE ANALYTICAL FIGURES AND EXPERIMENTS
text: A.1 COMPARISON OF LSH EFFICIENCY
Recall Definition 2.3 of the (k̃, ck̃, p1, p2)-LSH. It is known (Indyk & Motwani, 1998) that one can construct an LSH data structure with the worst case query time O(nR), where
R := log p1/ log p2
is called the LSH efficiency, which has been used in literature to theoretically compare different LSH methods, e.g. SimHash vs. MinHash (Shrivastava & Li, 2014). However, we found that in our case, the LSH efficiency does not provide much informative comparison of different LSH methods of interest. In Figure 7, we provide the LSH efficiency at multiple γ. Firstly, we see that the differences among the curves are very small. Basically, the figures tells us that SignRFF is always better than KLSH and SQ-RFF, but do not provide the comparison of SignRFF and KLSH regarding γ, as the ranking efficiency does. Also, the figures seem to suggest that SignRFF could (roughly) be better than LSH with large γ and large ρ, but it does not give a good threshold at around ρ = 0.7 (validated by the experiments) as suggested by the ranking efficiency. Thus, LSH efficiency is insufficient to well predict the practical search performance.
A.2 MORE EXPERIMENTS ON SEARCH PRECISION
Define N as the number of ground truth neighbors. The search recall and precision are defined as
recall@R = # true neighbors in R retrieved points
N ,
precision@R = # true neighbors in R retrieved points
R .
Consequently, by definition, recall@N is equivalent to precision@N. Therefore, in our experiments, i.e., Figure 3, Figure 5 and Figure 6, the curves are also “precision@N”. In Figure 8, we report more results on the search precision@R. As we can see, on SIFT, CIFAR and MNIST, the SignRFF method again performs the best as long as b ≥ 256. The comparison is fairly consistent with the recall (precision) curves presented in Section 5.
A.3 DATA PROCESSING TIME
Another benefit of SignRFF is its simplicity in implementation. This can be reflected in the data processing time. Note that, the query time consists of two parts: the processing time (to generate query binary codes), and the search time (to compare the query codes to the database). In our experiments, since we adopt the standard Hamming ranking method, the search time to return a fixed number of retrieved points are the same for all algorithms. Hence, we plot the comparison of processing time (for 1000 queries), as shown in Figure 9. We observe that SignRFF and LSH are the most efficient methods. KLSH is notably slower than SignRFF. The two data-dependent methods, SpecH and BRE, are significantly slower than SignRFF. This reveals a potential advantage of the simplicity of SignRFF in practical retrieval systems.

heading: B MORE IMAGE RETRIEVAL RESULTS ON CIFAR-VGG
text: In Section 5.3, we compare the locality-sensitive hashing methods with a deep learning based method, the Contrastive Information Bottleneck (CIB) (Qiu et al., 2021). CIB is built upon the pre-trained VGG-16 CNN model, whose objective is to generate binary representations such that images from the same class are close. Thus, same as many other deep hashing methods, the objective of CIB is slightly different from our setting (we find the most similar data points, without any label information), as being in the same class does not necessarily implies high similarity. In fact, in the empirical evaluation of many of these papers (e.g., Yang et al. (2019); Qiu et al. (2021)), the true neighbors are simply set as those data points with same label as the query. In our setting, we strictly follow the ranking to find the true neighbors with highest similarities. To better illustrate the difference, we present top-10 retrieval result of two queries (automobile and cat) in Figure 10. For SignRFF and KLSH, the retrieved images mostly have high similarity with the query, but may include some data points from other classes (e.g., truck vs. automobile, dog vs. cat). On the contrary, the retrieved images of CIB clearly have lower similarity with the query, but contain fewer other classes. This is largely because the VGG-16 is pre-trained by classification. Hence, in this experiment we set the true neighbors as the top-1000 similar data points, where CIB could be evaluated properly since most images from the same class would, at least, have not too low similarity.
C IMPACT OF THE DEPENDENCE IN KLSH
In practical implementation, the hash codes of KLSH are dependent. We give an intuitive explanation on how this dependence affect the search performance.
Firstly, let us review the reason why data-independent methods with independent codes (LSH, SQRFF, SignRFF) can boost search accuracy with increasing b. Essentially, same as the intuition of the rank efficiency, comparing Hamming distance is equivalent to searching for the data points with highest estimated hash collision probability using b codes. Let x,y be two database points and q be the query, with ρx > ρy . This means the hash collision probability px > py . We estimate the probability by averaging the collision indicators:
p̂x = 1
b b∑ i=1 1{hi(x) = hi(q)}, p̂y = 1 b b∑ i=1 1{hi(y) = hi(q)}. (13)
For data-dependent methods, with sufficient b, (12) gives the probability of wrong raking (i.e., p̂x < p̂y). We see that it strictly decreases with larger b.
Recall the steps of KLSH. We first sample m data points from database X , denoted as X̃ , to form a kernel matrix K. Then we uniformly pick t points, denoted as X̃′, from [1, ...,m] at random to approximate the Gaussian distribution. After some algebra, the hash code has the form
KLSH: h(x) = sign( m∑ i=1 w(i)k(x,xi)), (14)
where w = K−1/2et, and et ∈ {0, 1}m has ones in the entries with indices of the t selected points. To generate multiple codes, we use the same pool of points X̃ , but with different choice of et, i.e., X̃′ to approximate the Gaussian distribution.
Boosted performance with small b. For two hash codes hk and hk−1 of x, the k(x,xi) terms in (14) are the same. The w’s are dependent since the points used for Gaussian approximation (i.e. X̃′) may overlap. Thus, the conditional hash collision probability is usually larger than the unconditional one,
P (hk(x) = hk(y)|hk−1(x) = hk−1(y)) > P (hk(x) = hk(y)),
and it may increase as k get larger (intuitively, by dependence, more previous collisions implies higher chance of collision later on). Similarly,
P (hk(x) 6= hk(y)|hk−1(x) 6= hk−1(y)) > P (hk(x) 6= hk(y)).
Thus, at the beginning, the more similar (dissimilar) the data pair is, the more the estimator p̂ is upward (downward) biased. In other words, similar points would have further increased hash collision probability, while dissimilar points would have even lower chance of collision. This is the main reason that the empirical performance of KLSH is higher than theoretical prediction (where we assume independence) with short binary codes.
Slow improvement with large b. However, this is not the whole story. As more bits are used, there is less and less marginal information left. That is, the later generated codes would be more and more dependent on the previous ones. In an extreme case, at the point when all ( m t ) combinations of the t points in X̃′ have been used, the hash codes produced afterwards would all be the same as some previously generated ones, which would hardly improve the distance estimation anymore. This is why for KLSH, the recall curve becomes flat as b increases.

Review summaries:
The paper revisits the binary hashing from Random Fourier Feature (RFF) for approximate nearest neighbor search. The authors propose a simple and effective RFF-based hashing method SignRFF and demonstrate its locality-sensitive property. They also introduce a new measure called ranking efficiency to evaluate the performance of different LSH methods theoretically. Extensive experiments on three real-life image data sets validate the effectiveness of SignRFF and the consistency of the ranking efficiency from theoretical evaluation.

This paper proposed an improved version of Random Fourier Feature (RFF) based binary feature coding method as well as a new measure(ranking efficiency) to compare different Locality-Sensitive Hashing (LSH) methods. Under the new measure, the proposed method is better than previous methods. The authors also validated by visualization the consistency between theoretical comparisons based the proposed measure and the empirical results.

In this paper, the authors propose a simple strategy to extract random Fourier feature based binary codes. The authors also propose a new measure, ranking efficiency, to compare the search accuracy over two datapoints for locality-sensitive hashing methods. Experiments are conducted on several image retrieval datasets to validate the effectiveness of the proposed SignRFF.