Unleashing the Full Potential of Product Quantization for Large-Scale Image Retrieval
Authors: Yu Liang
Shiliang Zhang
Kenli Li
Xiaoyu Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Hash
Image Retrieval
Product Quantization
TL;DR: A novel deep hashing framework based on product quantization (PQ) for Large-Scale Image Retrieval

Abstract: Due to its promising performance, deep hashing has become a prevalent method for approximate nearest neighbors search (ANNs). However, most of current deep hashing methods are validated on relatively small-scale datasets, leaving potential threats when are applied to large-scale real-world scenarios. Specifically, they can be constrained either by the computational cost due to the large number of training categories and samples, or unsatisfactory accuracy. To tackle those issues, we propose a novel deep hashing framework based on product quantization (PQ). It uses a softmax-based differentiable PQ branch to learn a set of predefined PQ codes of the classes. Our method is easy to implement, does not involve large-scale matrix operations, and learns highly discriminate compact codes. We validate our method on multiple large-scaled datasets, including ImageNet100, ImageNet1K, and Glint360K, where the category size scales from 100 to 360K and sample number scales from 10K to 17 million, respectively. Extensive experiments demonstrate the superiority of our method. Code is available at https://github.com/yuleung/FPPQ.

Unleashing the Full Potential of Product Quantization for Large-Scale Image Retrieval
Yu Liangl
Shiliang Zhang?
Kenli Lilt
Xiaoyu Wang"t
CCollege of Computer Science and Electronic Engineering, Hunan University
National Key Laboratory for Multimedia Information Processing,
School of Computer Science, Peking University
The Hong Kong University of Science and (eahnolgg(Guunnghhuu) *Intellifusion Inc. fleungyu, 1k1) fechnu..edu.ccmm edu cn, slzhang jdl@pku jdl@pku.edu.cr, edu. fanghuaxue@gmail..om
Abstract
Due to its promising performance, deep hashing has become prevalent method for approximate nearest neighbors search (ANNs). However, most of current deep hashing methods are validated relatively small-scale datasets, leaving potential threats when are applied to large-scale real-world scenarios. Specifically, they be constrained either by the computational cost due to the large number of training categories and samples, or unsatisfactory accuracy. To tackle those issues, we propose novel deep hashing framework based on product quanti- zation (PQ). uses a softmax-base predefined PQ codes of the classes. Our method is easy to implement, does not involve large-scale matrix operations, and learns highly discriminate compact codes. We validate our method on multiple large-scaled datasets, including Ima- geNet100, ImageNetIK, K, and Glint360K, where the category size scales from 100 360K and sample number scales from 10K 17 million, respectively. Exten- sive experiments demonstrate the superiority of our method. Code is available at
differentiable PQ branch to learn a set
Introduction
Approximate Nearest Neighbors Search (ANNs) aims quickly find necessary information within
vast amounts of data. It is commonly used in image and video search [49, 37, recommendation systems [44, 8), and anomaly detection [34, 1] tasks. Hashing [18, 7, 16, 37]. which is key component of ANNs, has been continuously and rapidly developed over time. Hashing enables the efficient mapping of high-dimensional floating-poin data into binary code, with the main objective of minimizing storage space and retrieval time while maintaining satisfactory retrieval accuracy.
In the past decade, researchers have been exploring the use of deep learning to optimize hash tech- nology for improved retrieval performance [18, 23, 7, 27, 12, 48]. Compared to traditional methods, deep hashing has shown significant improvement. Nevertheless, to the best of our knowledge, existing deep hash or deep quantization methods have not been comprehensively tested in large-scale data retrieval scenarios, which are commonly encountered in real-world applications. For example, in face recognition [9, 2, 52, 39, 29], where the underlying databases may contain millions categories and hundreds of millions of samples. The large-scale datasets pose higher requirements to the
'ork done as intern Intellifusion. Corresppnning authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

efficiency of learning and inference, as well as the accuracy of deep hashing algorithms, As shown in our experiments, when tested on large-scale dataset, the classic product quantization (PQ) [20] outperforms many deep hashing methods.
As the one of the most popular methods for quantization retrieval, PQ, however, shown in Fig. 2, its retrieval performance rapidly declines as the encoding length decreases, rendering it impractical in some applications. Shorter PQ codes can improve retrieval speed and reduce storage overhead, greatly expanding its use, for example, making it a more viable option for edge devices. Due to PQ's widespread use in various industrial applications and its advantages in large-scale data compared to other hash methods, we hope to further unlock the potential of PQ and use it for real-world large-scale image retrieval scenarios. Our objective to address the challenge that PQ's performance rapidly decays with code length by obtaining feature representation of the database that is better suited for cluster assignment in multiple sub-spaces. We hold the view that the poor performance of short PQ codes stems from insufficient clustering conditions in the subspace of the original feature vector, resulting in excessively large quantization errors and high error rates during retrieval.
Building on the aforementioned discussion, we propose an end-to-end deep product quantization method called FPIQ(Full Potential Product Quantization). Our approach is simple and intuitive: for the large-scale dataset, we generate a PQ code for each class, which is then utilized as a label for learning via differentiable multi-segment fully connected branch. Upon completing training, the retrieval process is precisely the same as that of traditional PQ, allowing for easy integration into current mature retrieval modules.
The contribution of this paper can be summarized as three fold. Firstly, for the first time, we investigate the retrieval performance of current popular or advanced deep hash methods under extremely large datasets with an extensive number of categories and demonstrate that they may not be suitable for such scenarios. Secondly, we propose simple yet effective end-to-end deep feature quantization compression method, based on class-level product quantization coding supervision. Our method achieves a low-slope decay of retrieval performance with decreasing code lengths and can be used for retrieval in the same way as the traditional PQ. Finally, we conducted extensive experiments on Glint360K [2], a large-scale datasets with 360k classes and 17 million images, as well as two relatively smaller scale datasets, ImagenetIK [35] and Imagenet1 00 [7, 35]. The results demonstrated the effectiveness of our method.
2 Related Works
Hash technology is widely used for compressing data and speeding up retrieval processes in computer vision. The goal is typically to ensure that samples that are similar in their original space remain similar when they are mapped to the new hash space. Researchers have conducted extensive research on hash technology recent years, and hash methods can be classified in several ways.
For example, hash methods can be categorized according to the calculation method of hash distance. Hamming distance-based methods aim to learn binary code and calculate the distance between samples using the Hamming distance metric [16, 19, 32, 42, 46, 18, 37, 12, 25, 24, 40, 7, 36, 26]. Conversely, dictionary- based methods calculate distance by looking up a table through codebook [20, 51, 15, 28, 13, 27, 23, 49, 45].
In alternative way, hash methods can be categorized into non-deep and deep methods. Non-deep methods such as LSH [16], Composite Quantization (CQ) [50], Additive Quantization (AQ) [3], PQ [20]. OPQ [14], LOPQ [21] are widely used for efficient retrieval. LSH is data-independent random locality sensitive hash algorithm that can use a variety of methods such as random projection or buckets directly perform hashing. PQ clusters the sub-vectors and represents original vectors by the cluster categories. OPQ and LOPQ improve upon PQ by transforming the original data to reduce quantization error and considering the local relationships of the vectors, respectively. Non-deep hashing methods have higher efficiency but lower performance, while deep hash methods leverage the powerful representation learning abilities of neural networks to learn hash codes and feature representations simultaneously, reducing quantization error for better performance [18, 49, 37, 23, 45, 27, 47, 48, 51]. Since the quantization process is not differentiable, researchers often employ the sigmoid function or tank function to fit the sign function [7], or use the straight-through (ST) estimator [5] to avoid gradient non-transfer, as in the case of DPQ [23] and GreedyHash [37]. For more detailed information deep hashing, please refer to [30].
2

---

Limitation: Despite the existence of many hashing methods with their own unique advantages, they unfortunately have limitations when applied large-scale datasets. For example, in the face of large-scale data, the Gini Impurity related penalty constraint item designed by DPQ [23] is difficult to apply and can easily cause network collapse, leading to a large number of data being mapped to the same code. In terms of computing resources, PQN [45] and DTQQ [27] are computationally expensive due to the construction of triples, despite DTQ proposal to reduce the amount of calculation by dividing the dataset into multiple groups. DQN [47] requires frequent clustering of the entire training data to update the hash code center. Recent works attempt to apply deep hashing to large-scale datasets with thousands of classes, such as OPQN [49], ADSVQ [51], DCDH [48], etc. However, ADSVQ and DCDH need to calculate a square matrix of the number categories in the training process, which limits the further expansion of the number of categories in the dataset. The number of bits in OPQN is limited to the feature dimension, resulting in significant training overhead when a longer bit number is needed to ensure retrieval performance. In contrast, method does not involve large-scale matrix operations, converges quickly, and overcomes the limitations of previous methods for large-scale datasets.
3 Preliminaries
Denoting the input images as I and the deep features set extracted by the backbone as F E "),, Product Quantization divides the feature F into M segments, i.e., F == [F F Fm. Fm......
FM]] where Fm E DD/M, Within each segment, all sub-vectors {Fm } are clustered into K categories using the k-means algorithm. Consequently, each feature can be repre- sented as an M-tuple: PQ(F)= = [h,,... Am,- k,L), where each kim represents the clustering cideg) of the m-th sub-vector and ranges from to - The codebook C E R RMx X (D/M) consist of the clustering centers in each of the M segments, which are used to reconstruct the original features from the M -tppl representation PQ(F):
quant( (F) = [c],
where quant(F) is the quantized vector that approximates the original feature F, and CK., denotes the -ih codeword in the m-th part of the codebook. Finally, the feature is compressed into M x b bits.
In retrieval phase, Lookup Tables (LUTs) will be calculated, which stroed the distances between the query and the codebook elements. Then, the distances between the query and all samples in the gallery set can be efficiently computed by looking up the LUTSs.
Method
4.1 Overview
The original PQ method is designed to minimize quantization eтror using clustering algorithms. However, when we increase the compression strength to reduce the encoding bits in PQ, the number of segments M decreases, and the sub-vector dimension increases, which brings problems: 1) The impact of misallocation of segment increases: the quantization error will increases with the sub-vector dimension increases, and also the importance of a single segment will increases with the number of segments decreases. 2) As the number of segments decreases and the sub-vector dimension increases, the sub-vectors become more like complete features, usually with stronger discriminative. Therefore, the sub-vector distribution becomes more uniform. Since we need to assign N classes to K clustering centers, where N >> K 2¹, this makes it more likely for features of different classes to be assigned to the same PQ codes, or for the same class to be assigned to different PQ codes. These problems will significantly affect PQ performance.
To mitigate those issues, we train a backbone to generate features that are better suited for short PQ encoding, Our aim is to assign features of the same class to the same PQ code and cluster the sub-vectors that belong to the same encoding within each sub-space. To achieve these goals, we undertook these two actions: 1) learning a backbone to generate features that better suited for short PQ encoding based on a set of pre-defined class-level PQ code supervision, and 2) using the learned adaptable codebook to guide the PQ encoding process.
3

---

Learinng CodetBook
Training
Label
Retrievul Phase
Phase
Feature
Fi
JC
Lyn
Backbone
Query
Fss
iPcy
K2
Scarch
Leamed CodaBook
Backhone
Database
Leuredd CodeBBook
Gallery Set
Far
Kar
Cinces
Result
Ligh
Cluss
Figure 1: The overall flow of our framework. It consists two branches during the training phase: one-hot classification branch for the entire feature and another PQ classification branch that constrains sub-vectors of the feature. We use the predefined class-level PQ labels to guide the learning of the PQ branch and improve feature separation in sub-spaces. During the retrieval phase, the only difference with traditional PQ is that our framework does not require clustering for the codebook. Instead, we directly use the learned codebook obtained from the PQ branch, which comprises the fully connected weights of multiple sub-branches in the PQ branch.
Fig. illustrates the overall flow of our framework. We incorporate PQ branch at the end of the backbone and run in parallel with the classifier. To learn the PQ code targets for each class, we divide the features F into M segments refer to the PQ encoding process. For each PQ sub-branch we maximize the posterior probability of the ground-truth:
M
1
Lpy
log
BM
=k=1 6Fmmk
where B is the batch size, M the number of PQ code segments, and K is the number of clusters in each segment. 2mk is the output of the k-th unit in the m-th PQ sub-branch. k' is the ground-trui value, which the code value of a unit the PQ label.
Optimizing Sub-branches with Angle: Let us consider the Fuclidean distance between the sub- vector Fm. the m-th segment and K classification weights (Wmki k K]} belonging to the m-th PQ sub-branch:
D Duucidean ( (Fms Wink) - 1m ||
|| [mma cos 6ynks
(3)
where Omk is the angle between Wink and the sub-vector F.. We normalize {wink] by setting [/m = 1, Then, Eq. (3) can be interpreted as:
DEuctideon (Fms Wmnk V - Fm cos 0nk-
(4)
Now, the ranking of the Euclidean distance between the sub-vector Fm in the m-th segment and all the weights {won) in the corresponding PQ sub-branch depends solely the angles {6mki 9 E [0. T This is because the norm of Fm. denoted |.F ll. is invariant to changes the magnitude of the weights (wnk). Exploiting this property, we can optimize M softmax sub-branches based the angles. To further stabilize the training process and accelerate model convergence, we omit the bias term in the FC layer. Additionally, normalize Fm and set [ 1. This get:
Zmk
Fm |mmlllll cos 0 = cos 0
(5)
Retrieval tasks typically demand higher degree of discriminability than classification tasks. simple softmax cross-entropy loss may fall short of achieving the desired results. To enhance the discriminability each sub-branch, margin can be added to the loss. Fortunately, we can utilize existing metric learning losses [39, 9, 29] such as CosFace [39] to successfully achieve our objectives:
B log
(B mak -margin))
Log BM
(6)
clcoss( mid +margin)))) + > 1e e cos(0mk))
+K

---

where margin 2 0 is fixed parameter to control the magnitude of the cosine margin, and s is scaling factor.
Apart from the PQ branch, the classification branch is also utilized to enhance the discriminability of the full features. The final optimization objective is defined
L Lets Lpp:
where Lads denotes any classification loss used to learn the backbone, and we can achieve the optimization objective in end-to-end manner.
4.2 Predefined Class-Level PQ Label
Earlier works have utilized predefined hash codes as labels for guiding model learning, such as DPN [12], CSQ [46]. and OrthoHash [18]. They constructed hash codes via Hadamard matrix [41] or Bernoulli sampling to uniformly distribute the hash codes in the target space and maximize the distance between the hash codes. However, the number of data categories increases, the large dimensions of Hadamard matrix make it impractical to use, and achieving near-uniformity of compressed hash codes based Bernoulli sampling supervised target can be difficult to converge.
In our approach, we get the class average featurew {Favg) } for each class by averaging the output features of a pre-trained model. Here, we assume that the classifier of the pre- pre-trained model has been discarded and is not usable, this is common scenario, particularly in retrieval tasks. We then execute the PQ encoding process on {Faeg] } by performing k-means [31] clustering in each sub-space to generate the corresponding class-level PQ encoding. These PQ codes implicitly capture inter-class relationships:
PQlabel PQ((Faug))
8
= [[k,, km.. ..... kkslas' cls E [1, class class_num]]
In situations with a lot of data categories and low encoding bits, there a risk of PQ code duplication. To remove duplication and ensure meaningful inter-class relationships. remove such duplicates by assigning them to the position with the lowest quantization error, provided that the position is not already occupied by another PQ code.
4.3 Encode and Retrieval
After completing the training phase of our framework, we utilize the backbone to extract the feature representation of the input images I. The PQ branch weights, which consist of M FC layers, used as the codebook in the PQ algorithm to obtain the PQ code the gallery set and calculate the quantized distance. Specifically, we extract the weights of the PQ branch and perform normalization on them as follows: Wmk f- Wmnk/ [[wmlll Wmm IR D/M All Wink of the M K items in the M branches are combined to codebook, denoted as C E (DD/M) where C. Wmnk At this point, the PQ algorithm no longer requires training, and the codebook C learned during the training phase will be used to initialize the PQ algorithm. We can encode the samples of the gallery set as PQ(Fg) = {[k1,-
Am. ... kM [1, 11,mumimmaa nrum_images]..
There are two methods of utilizing PQ for retrieval: symmetric retrieval and asymmetric retrieval. When apply symmetric retrieval, the distance between samples in the query set and the gallery set calculated as follows:
D sym Σ
(Cink Conke)
where h* is the index of the closest codeword to sub-vector Fn among the K codewords in the m-th part the codebook, and Cmk- and Cynk+ represent the quantized representation of the m-th segment of the query sample and the gallery sample, respectively. When apply asymmetric retrieval, the distance between samples in the query set and gallery set calculated as follows:
M
Dasym
Iquery C.nks)
(10)
m=1
5

---

where Fiuery is the sub-vector of the m-th segment of the query sample. Considering the discussion
about Eq. (4), we have:
k arg min (Fm: Cmk)
ke
(11)
arg min (Fm; Cmnt:;
K-
where Fi is the normalized vector of Fm and (o) can be either the cosine distance or the Euclidean distance. Referring to Eq. (II), for symmetric retrieval, no additional feature operations are necessary for encoding, even though we perform segment normalization When apply asymmetric retrieval, Em=1 (Fquery ,Cnkk)) ) # Em=1 (Fquery, C.ass), ) the retrieved results may be different. However, as Cma=+ is a certain value and the classification loss with margin of PQ branch increases the compactness of the encoding,
the features during training phase.
found in our experiments that whether applying segment normalization operations for the feature had little impact on the ultimate retrieval performance. The same conclusion holds for the normalization of full features, despite the intuition that normalizing the complete features can enhance the stability of asymmetric retrieval results by fixing the magnitude of || Fm Overall, whether applying symmetric or asymmetric retrieval, we do not need to perform any additional processing on the features compared with PQ algorithm.
5 Experiment
5.1 Datasets and Evaluation
Although our primary focus is to evaluate the performance of the proposed hash method large- datasets, we will validate our approach on datasets of various scales, including a large-scale datasets Glint360K, as well as two relatively smaller scale datasets, ImageNet100 and ImageNetIK.
Glint360K [2]: Glint360K is one of the largest publicly available face datasets, with over 360K IDs and 17 million images. We use all available data to train hash methods and test for convergence by evaluating the unseen retrieval performance on two other datasets, MegaFace [22] and FaceScrub [33], which are non-intersecting with Glint360K.
MageFaac and FaceScrub; MegaFace is a dataset of one million images that capture over 690K different individuals and will be used as the gallery set. FaceScrub comprises over 100K photos of 530 celebrities. Following [22], the evaluation was performed on subset of FaceScrub that includes 80 individuals (40 females and 40 males) from individuals with more than 50 images each. We followed the recommendations from insightface project' to remove noise and duplicate samples. The final query set consists of 3529 face images from 80 different individuals.
ImageNet1K [35] and ImageNet100: ImageNet1 K is widely-used large-scale visual recognition challenge dataset, which contains 1000 classes and over 1.2 million images. We employed the training set of ImageNetI images, to evaluate hash retrieval performance. Specifically, we selected the top 5 images from each class in the validation set, totalling 5000 images, construct the query set, while the remaining 45,000 images comprised the gallery set. ImageNet100 has been popularly used in previous deep hashing methods [46, 18, 7], and is the subset of ImageNetIK, consisting of 100 classes.
train the hash methods and used the validation set, which consists of 50,000
Evaluation: In the following experiments, we will use asymmetric retrieval and our method will not perform any feature preprocessing during retrieval. We will assess the retrieval performance using 1op-1, Top-5, and Top-20 accuracies on the Glint360K datasets. Specifically, the query set consists of N individuals, and for each individual, incorporating it into the gallery set and employing each of the other M-1 images as the query set. Regarding ImageNetlK and ImageNet100. we will assess the retrieval performance by using the mean average PP)) of the top 1000 result: MAP@ 1000.
have M images. We will test each image by
5.2 Implementation Details
All experiments were conducted using the PyTorch framework and 8 NVIDIA 2080Ti or 3090Ti GPUs for training. We employed a pre-trained model to get features so that we could acquire

---

Table 1: On the large-scale dataset Glint360K, the performance comparison of multiple methods under multiple code lengths, it should be noted that some methods were not listed due to ineffective performance or requiring unrealistic computational resources.
Glint360K
iResnet50
32 bits
64 hits
128 bits
Method
Top-1
Top-5
Top-20
Top-1
Top-5
Top-20
Top-1
Top-5
Top-20
PQ [20]
0.1724
0.2999
0.4254
0.6665
0.7749
0.8404
0.9184
0,9492
0,9610
HHF [42]
0.0001
0.0014
0.0054
0.0773
0.1646
0.2661
0
0
CSQ [46]
0.0061
0.0113
0.0183
0.0124
0.0197
0.0269
0.0283
0.0372
0.0451
OrthoHash [18]
0.3098
0.3706
0.4171
0.5526
0.6007
0.6351
0.6626
0.7104
0.7454
GreedyHash [37]
0.3688
0.5220
0.6323
0.6102
0.7452
0.8251
0.8259
0,9003
0.9338
FPPQ(Ours)
0.9343
0.9601
0.9652
0.9467
0.9571
0.9628
0.9568
0.9690
0,9731
class-level PQ labels. is worth noting that this operation is fair since other comparative methods also use this pre-trained model to initialize their model parameters. In all experiments, we set the hyperparameters 8 to 64 and margin 0.2. Moreover, we set 8 bits per segment, which is the commonly used setting in practical applications. This implies that the number of categories K per sub-branch was set 256, while the number of segments varied depending on the target bits. For example, the bits [16-bits, 32-bits, 64-bits, 128-bits] corresponded to the segments [2. 4, 8, 16]. We compared various hashing methods [20, 7, 46, 12, 25, 48, 36, 18, 23, 42, 43], and we implemented these methods based on the cisip-FIRe project and integrated some public projects provided by the specific author. For a fair comparison, we use the default settings in the cisip-FIRe project or used the default hyperparameters specified in their papers, and we trained all methods with the same backbone, same epochs, and same batch sizes, among others. In general, unless otherwise specified, these methods we compare are trained using fine-tuning based on the pre-trained model, and the hash layer had an initial learning rate of 0.0001 that decreased to 0.00001 after training 0.8 times number of epochs. The backbone learning rate was always 0.1 times that of the hash layer. In the following experiments, we will provide more specific explanations regarding implementation details.
5.3 Results on Large-Scale Dataset Glint360K
Implementation Details Supplement: We employed iResnet [11] as the backbone and adopted
the default training settings from the insightface project. The dimension of features output by the backbone was set to 512. We employed SGD as the optimizer with a weight decay of 0,0001. The batch size was set to 128 x 8, and the model was trained for total of 20 epochs. The initial learning rate was set to 0.1 and linearly decreased it to 0 based on the number of training steps.
Comparison: We explored and tested various advanced methods, including PQ [20]. HHF [42]. CSQ [46], OrthoHash [18], GreedyHash [37], JMLH [36], DPQ [23], DCDH [48), DWDM [10), etc. These methods can be considered encompassing the current most competitive hashing methods. However, DCDH and DWDM were abandoned due to exceeding computational resource limitations with large-scale matrix multiplication, JMLH and DPQ did not achieve effective performance. The further restricted methods are explained in Sec. 2. It should be noted that OrthoHash also applies a similar angular loss function for model optimization. To enhance its feasibility on large-scale data, we set its hyperparameters to 64 and margin to 0.2, the reason please refer to [39]. For methods that used predefined hash centers [46, 18]. we used Bernoulli sampling and ensure that hash centers were non-redundant. This approach is chosen due to the inefficiency and infcasibility of generating hundreds of thousands, or even millions, of hash centers using the technique proposed in OrthoHash. We only demonstrate methods that achieved certain level of performance in Tab. 1.
As it is apparent, currently available methods fail achieve satisfactory performance on large-scale datasets under multiple bit settings. The hyperparameters in HHF change depending on the minimum distance bound tables proposed in [6] for different code lengths, which hinders its efficacy to converge in 128 bits. While OrthoHash and GreedyHash have achieved a certain level of performance, they have exhibited inferiority to the original PQ method in both 64 bits and 128 bits. In contrast, our proposed method has displayed significant performance improvement under multiple bit settings.
7

---

Table 2: Under different network structure and bits settings, our method achieved consistent and significant improvements.
Glint360K
Backbone
iResnet18
iResnet50
iResnet100
Method
Metric
128 bits
64 bits
32 bits
128 bits
64 bits
32 bits
128 bits
64 bits
32 bits
Top-1
0.8005
0.4588
0.0973
0.9184
0.6665
0.1724
0,9465
0.7380
0.2074
PQ [20]
Top-5
0.8659
0,5958
0.1940
0,9492
0.7749
0.2999
0.9658
0.8378
0.3569
Top-20
0.9025
0.6903
0.3031
0.9610
0.8404
0.4254
0.9720
0.8878
0.4941
Top-1
0.8231
0,7019
0.6945
0,9568
0.9467
0.9342
0.9679
0.9578
0,9305
FPPQ(Ours)
Top-5
0.8824
0.7890
0.7576
0.9690
0,9571
0.9601
0.9746
0.9728
0,9700
Top-20
0.9133
0,8414
0.8006
0.9731
0.9628
0.9652
0.9772
0.9753
0.9734
RI5 PQ)
E25-20
32.
Comgrooim Fifiiiency
(a) PQ
(b) FPPQ
Figure 2: In Glint360K, comparison of the asymmetric retrieval performance trend of PQ with compression effi- ciency and the results of our methods for improving quality. 'L.2' represents using the original features for 1.2 re- trieval, while 'M=256' represents divid- ing each feature into 256 segments for PQ retrieval, and 8 bits per segment.
Figure 3: The visualization of the sub-vectors and cluster- ing centers for the 10k classes in the Glint360K dataset of two approaches: (a) classification loss with PQ and (b) our proposed method. The black dots represent sub- features, while the red dots in (a) depict the clustering centers obtained by performing k-means clustering on the sub-features of all classes. In contrast, in (b), the red dots represent the codewords trained by our proposed method.
Specifically, in the 32-bit setting, our method outperformed GreedyHash with a nearly 57% increase in Top-1 performance. Additionally, we were able achieve approximately 28% and nearly 4% performance growth in the 64 bits and 128 bits settings, respectively.
Performance with Different Backbone Settings: We also tested the effectiveness of our method under multiple network structures, and our method achieved significant advantages in all results, as shown in Tab. 2. Noting that the large-scale datasets provided favorable conditions for PQ clustering, making PQ a strong baseline, as evident in Tab. 1. Therefore, in this comparison, we focused on comparing our method with PQ (additional results can be found in the supplementary material). We can observe that larger backbones typically result in better performance. However, iResnet100 did not consistent improvement in comparison to iResnet50 when encoded to 32 bits (Top-11. Top-5t, Top-201). we suspect that the performance limits of the 32 bits setting may be due to the intrinsic constraint of compression strength.
Low-Slope Decay of Retrieval Performance: As the encoding bit-length decreases, the performance of naive product quantization encoding experiences significant decline. However, after being trained using our proposed method, the performance degradation gradually occurs at a lower slope with decreasing bit-lengths due our approach's performance improvement at low bit-lengths. This trend is illustrated in Fig. 2.
t-SNE Visualization: To better illustrate the effectiivnness of our proposed method, we utilize t-SNE [38] to visualize changes in sub-vectors when the feature are compressed to 32 bits. For visualization purposes, We select the first segment of the average features of the first 10,000 classes in Glint360K, denoted as {Fi) } E 100000X(DMM) and their corresponding codewords for the first part, represented by C1 E IR K (D(M/))
As we can in Fig. 3, the sub-vectors of the original features tend to be

---

Ours
PQ4F
PQI-Fhor
Query
Target
PQ4-F
Ours
PQ4-8
PQ4-Iner
PQurSeaFoor
Query
Target
PQL-F
Figure 4: Visualization of the Top-20 retrieval samples using FaceScrub as the query set and MegaFaac the gallery
evenly distributed throughout the subspace, hindering sub-vectors compression. In contrast, our method effectively learns class-level PQ labels, leading the sub-vectors cluster into K clusters in the subspace.
Retrieval Result Visualization: Moreover, we provide visualizations of the Top-20 retrieval results on the MegaFace and FaceScrub datasets in Fig. 4. This encompasses comparisons between various ways: 1) method, which includes 1.2 retrieval and PQ4 retrieval (without feature processing, normalization, or segment normalization), and 2) the original 1.2 retrieval and naive PQ4 retrieval (with or without feature normalization). It can be observed that our method generates similar top-20 results under different feature preprocessing settings, further validating the insensitivity of our method feature preprocessing.
5.4 Results on Smaller Scale Datasets
In addition to conducting experiments on large-scale datasets, evaluated our proposed method on relatively small datasets such as ImageNet1 and ImageNer100. We utilized ResNet50 [17] as the backbone and employed parameters pre-trained on ImageNetIK to initialize the model. The dimension the features output by the backbone 2048. Our experiments on these datasets not only demonstrated the effectiveness of our proposed method but also allowed to make preliminary attempts at addressing two special scenarios.
Results on ImageNNet10:: The experiment on ImageNet100 highlights scenario where the data scale is small and has fewer categories compared to the number of clusters required for k-means clustering. As k-means clustering cannot be executed in this scenario, we overcame this limitation by training the PQ using all instance features and subsequently encoding the class average features. To prevent overfitting due to the limited data, we fixed the backbone and added linear layer of 2048 to 128 at the end the backbone for learning. We fine-tuned our model for 100 epochs with a learning rate of 0.0001. The results presented in Tab. 3, and the performances of other methods were obtained either by replicating the results using the cisip-FIRe project or citing their respective papers. Our method achieved the best performance ImageNet100, indicating its efficacy in scenarios involving limited dataset scale.
Results on ImageNet1K: The experiments on ImageNet1 K reveal another scenario: the inability to obtain a good class-level PQ label due to limitations discrimination. With only 1000 classes in ImageNet1K K, training PQ effectively becomes challenging given the limited number of categories available. Moreover, the low discriminabilityy between classes in the features generated by pre-trained model leads to significant amount of duplicate PQ codes
number of training samples or low feature

---

Table mAP@RI000 on ImageNet100
ImageNet100 mAP
@1000
@
Method
bits
32 bits
bits
HashNet [7]
0.5101
0.7059
0.7997
CSQ [46]
0.8379
0.8750
0.8874
DPN [12]
0.8543
0.8799
0.8927
DFH [25]
0.8352
0.8781
0.8849
DCDH [48]
0.7856
0.8158
0.8400
JMLH [36]
0.8366
0.8671
0.8799
GreedyHash [37]
0.8544
0.8796
0.8886
HBS-RL [43]
0.8465
0.8702
0.8851
DPQ [23]
0.8860
0.8770
0.8660
HHF [42]
0.8710
0.8910
0,8960
OrthoHash [18]
0.8693
0.8869
0.8994
FPPQ(Ours)
0.8956
0,9128
0.9154
after PQ training and encoding. For instance, duplicate rates can exceed 50% for the PQ codes of 1000 class average features when compressed to 32 bits. To tackle this issue, we adopt the method proposed by OathoHash, which involves generating hash codes using repeated Bernoulli sampling to achieve binary encodings with sufficient hamming distance. These binary encodings are then segmented and converted into decimal codes to serve as PQ labels. We adopts the default training strategy from the cisip-FIRe project, fine-tuning for 90 epochs. we compared several of the most competitive methods and the experimental results are presented in Tab. 4. As shown in the results, our method achieved competitive results, particularly when the encoding length was relatively short.
Table 4: mAP@ R100 on ImageNetI
Image
mAP
@ R1000
Method
16 bits
32 bits
64 bits
HHF [42]
0.2961
0.5979
0.6121
DCDH [48]
0.3666
0.4764
0.5299
CSQ [46]
0.5040
0.6061
0.6093
JMLH [36]
0.5286
0.5876
0.6098
GreedyHash [37]
0.5424
0,5896
0.5952
OrthoHash [18]
0.5936
0.6514
0.6761
(PPQ(Ourr)
0.6207
0.6543
0.6649
Conclusion
This study explored and evaluated several advanced deep hashing methods for large-scale image retrieval, identifying their limitations. In addition, we proposed product quantization-basel frame- work that employs multiple softmax branches to learn specific class-level PQ labels. Our proposed method effectively performs during the retrieval stage and aligns well with the traditional product quantization methods. Notably, our method is independent of the number of classes and data samples required, requiring only an additional parameter quantity of K and relatively small amount of computational resources. Therefore, our proposed method offers promising prospects for large-scale image retrieval tasks.
Ethics Statement
This paper primarily focuses on hash technology, aiming to enhance data compression and retrieval while extending current deep hash methods large-scale scenarios. The datasets we utilize are publicly available, and we ensure strict adherence their respective open licenses.
10

---

Acknowledgement
This work is supported in part by the National Key Research and Development Program of China under Grant No. 2021ZD40303; in part by the Natural Science Foundation of China under Grant No. U20B2052, 61936011; I; in part by the National Key Research and Development Program of China under Grant No. 2018YFE01 18400; in part by the National Natural Science Foundation Innovation Research Group Project under Grant No. 62321003.
References
[1] Leman Akoglu, Hanghang Tong, Danai Koutra. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, 29:626- (888, 2015.
Xiang An, Xuhan Zhu, Yuan Gao, Yang Xiao, Yongle Zhao, Ziyong Feng, Lan Wu, Bin Qin, Ming Zhang, Dehing Zhang, et al. Partial Training 10 million identities on a single machine. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1445-14499 2021. 1,
Artem Babenko and Victor Lempitsky. Additive quantization extreme vector compression. Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 931-938, 2014.
[4] Bain, Arsha Nagrani, Güi Varol, and Andrew Zisserman. Frozen in time: A joint video and image encoder for and-to-end retrieval. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages
2021.
[5] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.3432, 2013. 2
[6] Andries E Brouwer Tom Verhoeff. An updated table minimum-ddstanne bounds for binary linear codes. IEEF Transactions on Information Theory, 39(2):662-677, 1993.
Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip Yu. Hashnet: Deep learinng hash by continuation. In Proceedings of the IEEE international conference on computer vision, pages 5608 5617, 2017. 1, 6, 7,
Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of 10th ACM conference on recommender systems, pages 191-198, 2016.
[9] Jiankang Deng. Jia Guo, Niannan Xue, and Stefanos Zafeiriou. Arcface: Additive angular margin loss for deep face recognition. Proceedings of the IEEF//VV conference on computer vision and pattern recognition, pages 4690-4699, 2019. 1,
[10] Khoa D Doan, Peng Yang. and Ping Li. One loss for quantization: Deep hashing with discrete wasserstein distributional matching. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9457-9457, 2022. 7
[11] Ionut Cosmin Duta, Li Liu, Fan Zhu, and Ling Shao. Improved residual networks for image and video recognition. 2020 25th International Conference on Pattern Recognition (ICPR), pages 9415-9422.
IEEE, 2021. 7
[12] Lixin Fan, Kam Woh Ng. Ce Ju, Tianyu Zhang, and Chee Seng Chan. Deep polarized network for supervised learning accurate binary hashing codes. In IJCAI, pages 825-831, 2020. 1, 2, 7, 10
[13] Lianli Gao, Xiaosu Zhu, Jingkuan Song. Zhou Zhao, and Heng Tao Shen. Beyond product quantization: Deep progressive quantization image retrieval. arXiv preprint arXiv:1906.0 06698, 2019. 2
[14] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE transactions pattern analysis and machine intelligence, 36(4):744-755 2013.
[15] Allen Gersho and Robert M Gray. Vecior quantization and signal compression, volume 159, Springer Science & Business Media, 2012. 2
[16] Aristides Gionis, Piotr Indyk, Rajecv Motwani, et al. Similarity search in high dimensions via hashing. In Vidb, volume 99, pages 518-529 1999. 1,2
[17] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.

---

[18] Jiun Tian Hoe, Kam Woh Ng. Tianyu Zhang, Chee Seng Chan, Yi-Zhe Song, and Tao Xiang, One loss for all: Deep hashing with a single cosine similarity based learning objective. Advances in Neural Information Processing Systems, 34:24286-2444 24298, 2021. 1, 2, 5, 6, 7,
[19] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimen- sionality. Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-613 613, 1998. 2
[20] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, (3(1):117-125)) 2010. 2, 7,8
[21] Yannis Kalantidis and Yannis Avrithis. Locally optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2321-2328, 2014. 2
[22] Kemelmacher-S Shaiierr--Sliiemannn Steven M Seitz, Daniel Miller, and Evan Brossard. The megafuce benchmark: million faces for recognition at scale. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 4873-4882. 2016. 6
[23] Benjamin Klein and Lior Wolf. End-to-end supervised product quantization for image search and retrieval. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 5041- 5050, 2019. 1, 2, 10
[24] Wu-Jun Li. Sheng Wang, and Wang-Cheng Kang. Feature learning based deep supervised hashing with pairwise labels. arXiv preprint orXiv:1511.0385, 2015. 2
[25] Yungiang Li, Wenjie Pei, Jan van Gemert, et al. Push for quantization: Deep fisher hashing. arXiv preprint arXiv: TwE.199990000000 2019. 2, 7, 10
[26] Yunqiang Li and Jan van Gemert. Deep unsupervised image hashing by maximizing bit entropy. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 2002-2010, 2021.
[27] Bin Liu, Yue Cao, Mingsheng Long, Jianmin Wang, and Jingdong Wang. Deep triplet quantization. In Proceedings of the 26th ACM international conference on Multimedia, pages 755-763, 2018. 2,
[28] Meihan Liu, Yongxing Dai, Yan Bai, and Ling-Yr Yu Duan. Deep product quantization module for efficient image retrieval. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4382-4386. TERE, 2020. 2
[29] Weiyang Liu, Yandong Wen, Zhiding Yu, Ming Li, Bhiksha Raj. and Le Song. Sphereface: Deep hypersphere embedding for face recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 212-220, 2017. 1,4
[30] Xiao Luo, Haixin Wang, Daqing Wu, Chong Chen, Minghua Deng. Jianqiang Huang, and Xian-Sheng Hua. A survey on deep hashing methods. ACM Transactions on Knowledge Discovery from Data, 17(1):1-50, 2023. 2
[31] MacQueen. Some methods for classification and analysis of multivariate observations. In Proc. Sth
Berkeley Symposium on Math., Stat., and Prob, page 281, 1965.
[32] Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma. Detecting near-duplicates for web crawling. In Proceedings of the 16th international conference on World Wide Web, pages 141-150, 2007. 2
[33] Hong-Wes Wei Ng and Stefan Winkler. A data-driven approach to cleaning large face datasets. 2014 IEEE international conference on image processing (ICIP), pages 343-347. IEEE, 2014. 6
[34] Guansong Pang, Chunhua Shen, Longhing Cao, and Anton Van Den Hengel. Deep learning for anomaly detection: A review. ACM computing surveys (CSUR). 54(2):1-38 1-3 2021.
[35] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang. Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211 12211122222222 2015. 2, 6
[36] Yuming Shen, Jie Qin, Jiaxin Chen, Li Liu, Fan Zhu, and Ziyi Shen. Embarrassingly simple binary representation learning, In Procerseeeeee Proceedings of the IEEE/CVF International Conference Computer Vision Workshops, pages (00,2011 2019. 2, 7, 10
[37] Shupeng Su, Chao Zhang, Kai Han, and Yonghong Tian. Greedy hash: Towards fast optimization for accurate hash coding in enn. Advances in neural information processing systems, 31, 2018 1, 2, 10
12

---

[38] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008. 8
[39] Hao Wang, Yitong Wang, Zheng Zhou, Xing Ji, Dihong Gong. Jingchao Zhou, Zhifeng Li, and Wei Liu. Cosface: Large margin cosine loss for deep face recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5265-52744 2018. 1,4,7
[40] Xiaofang Wang. Yi Shi, and Kris M Kitani. Deep supervised hashing with triplet labels. In Computer Vision ACCV 2016: 13th Asian Conference on Computer Vision, Taipei, Taiwan, November 20-24, 2016, Revised Selected Papers, Part 13, pages 70 84. Springer, 2017.
[41] Eric W Weisstein. Hadamard matrix. https://matwoord. wolfram, com/ 2002.
[42] Chengyin Xu, Zenghao Chai, Zhengzhuo Xu, Hongjia Li, Qiruyi Zuo, Lingyu Yang. and Chun Yuan. Hhf: Hashing- bassingg-uiided hinge function for deep hashing retrieval, IEEE Transactions on Multimedia, 2022. 2,
10
[43] Xin Yao, Min Wang, Wengang Zhou, and Houqiang Hash selection with reinforcement learning for image retrieval. IEEE Transactions on Multimedia, 2022. 7, 10
[44] Xinyang Ji Yang. Lichan Hong. Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, neural modeling for large corpus item recommendations. In
Li Wei, and Ed Chi. sampling-bias-oomee Proceedings of the 13th ACM Conference on Recommender Systems, pages 269-277, 2019.
[45] Tan Yu, Junsong Yuan, Chen Fang, and Hailin Jin, Product quantization network for fast image retrieval. In Proceedings of the European Conference on Computer Vision (ECCV), pages 356-201, 2018. 2,
[46] Li Yuan, Tao Wang. Xiaopeng Zhang, Francis EH Tay, Zequn Jie, Wei Liu, and Jiashi Feng. Central similarity quantization for efficient image and video retrieval. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 3083 938-,309,,00 2020. 2, 5, 6,6, 10
[47] Cao Yue, M Long. Wang, Zhu Han, and Q Wen. Deep quantization network for efficient image retrieval. In Proc. 13th AAAI Conf. Artif. Intell, pages 3457-3463, 2016. 2,
[48] Ming Zhang, Xuefei Zhe, Shifeng Chen, and Hong Yan. Deep center-based dual-constrained hashing for discriminative face image retrieval. Pattern Recognition, 117:107976, 2021. 2, 10
[49] Ming Zhang, Xuefei Zhe, and Hong Yan. Orthonormal product quantization network for scalable face image retrieval. Pattern Recognition, page 109671, 2023. 1.
[50] Ting Zhang, Chao Du, and Jingdong Wang. Composite quantization for approximate nearest neighbor search. In International Conference Machine Learning, pages
PMLR, 2014. 2
[51] Chang Zhou, Lai Man Po, and Weifeng Ou. Angular deep supervised vector quantization for image retrieval. IEEE Transactions on Neural Networks and Learning Systems, 163441163,,, 2020. 2,3
[52] Zheng 7hu, Guan Huang, Jiankang Deng, Yun Ye, Junjie Huang, Xinze Chen, Jingang 7hu, Tian Yang. Jiwen Lu, Dalong Du et al. Webface260m: A benchmark unveiling the power of million-scale deep face recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition. pages 10592-10502, 2021.
13


Reviews:
[{"review_id": "vjlaNVK5kq", "reviewer": "Reviewer_kMZn", "summary": "This paper discusses a new deep hashing algorithm based on product quantization, which effectively addresses the issues of high computational cost and low accuracy. The algorithm successfully learns predefined PQ codes for different classes, achieving concise, efficient, and distinguishable codes. It has been validated on multiple large-scale datasets, including ImageNet100, ImageNet1K, and Glint360k, and has shown significant improvements.", "questions": "Does the method rely on a specific data distribution or dataset size? Is it applicable to different types of datasets or larger-scale datasets?", "limitations": "It is not clear whether this framework is applicable to non-visual tasks or non-image datasets as the validation is conducted on image datasets. Furthermore, the performance of this method on larger-scale datasets, such as those exceeding the size of the existing validation sets, is not explicitly explained.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It addresses the issues of applying deep hashing to large-scale data by providing an easy-to-implement method that does not involve large-scale matrix operations.", "weaknesses": "Training with the combination of two branches may increase the complexity and training time of the model. Additionally, the performance of the method depends on the selection of predefined PQ class labels, which is not extensively discussed in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n**Q1:The increase of complexity and training time.**\nIn fact, the number of parameters in the PQ branch is very small. Let $M$ denote the number of segments in PQ, $D$ denote the dimension of the embedded features, and $K$ denote the number of cluster centers. The number of parameters in the PQ branch is given by $M × (D/M) × K = D × K$, and the FLOPs (Floating Point Operations) is calculated as $M × (D/M + 1) × K = (D + M) × K$, which includes $D × K$ multiplications and $M × K$ additions. We have listed the specific computations and number of parameters in the following table. We assumed a relatively long code that we need to learn, where $M$ is set to 32, corresponding to learning 32 × 8 = 256-bit PQ codes, and $D$ is set to 512 with 256 cluster centers per PQ segment. As can be seen from the table below, the number of parameters and computations (FLOPs) of the PQ branch is very small compared to the backbone. It hardly increases the complexity and training time of the model. \n\n|  |  FLOPs  |       | Parameters |           |\n|--------|-------------|-----------|---|------|\n| |Backbone |PQ-Branch | Backbone  |PQ-Branch   |\n| iResnet18 |2634.12M |0.14M |24.03M |0.13M   |\n| iResnet50 |6346.83M |0.14M |43.59M |0.13M   |\n| iResnet100 |12149.32M |0.14M |65.16M |0.13M |\n\n\n**Q2: The select of the PQ label.**\nOur method seem is not particularly sensitive to the selection of PQ labels. We provide three pieces of evidence to support this claim:\n\n1)In our experiments on ImageNet1K, as ImageNet1K has just 1000 classes, PQ could not be effectively trained due to the small number of categories. Moreover, the low discriminability between clAverage featureasses in the features generated by a pretrained model leads to a significant amount of duplicate PQ codes after PQ training and encoding. Therefore, instead of training on class average feature to generate PQ label, we utilize the OrthoHash's method to generate hash codes, whereby the hash codes are assigned randomly. These hash codes are then segmented and converted into decimal PQ code labels. The experimental results in Table 4 of the original paper demonstrate that our method also achieves good retrieval results. \n\n2)Another experiment. We conducted involved using PQ4 labels generated by iResnet18 and iResnet100 to guide the training of iResnet50. The results of this experiment are presented in the table below. It can be observed that the retrieval performance in these settings is relatively consistent with the original setting. Note that using PQ codes generated by iResnet18 as labels resulted in better Top-1 performance compared to using PQ labels generated by iResnet100 and iResnet50. This observation aligns with the findings in Table 2 of the original paper, suggesting that PQ4 may have reached a performance bottleneck on the Glint360k dataset.\n\n|||Glint360k iResnet50||\n|:-------------------:|:---------:|:----------:|:-----------:|\n| Label  |    iR18-PQ4 | iR50-PQ4 | iR100-PQ4 |\nTop-1   | 0.9402 | 0.9342 | 0.9346\nTop-5   | 0.9611 | 0.9601 | 0.9609\nTop-20  | 0.9658 | 0.9652 | 0.9668\n\n3)We also conducted an additional experiment to further discuss the choice of PQ labels. Actually, it is  a part of our future work. In this experiment, we aimed to move away from predefined PQ codes and instead utilized the weights of the model's fully connected layer as class prototypes to iteratively construct PQ codes during the training process. The obtained experimental results, shown below, demonstrate similar performance compared to the current methods.\n\n|||Glint360k iResnet50||\n|:-------------------:|:---------:|:----------:|:-----------:|\n|  |   PQ4 |PQ8 | PQ16 |\nTop-1   | 0.9369 | 0.9460 | 0.9682\nTop-5   | 0.9628 | 0.9702 | 0.9738\nTop-20  | 0.9676| 0.9723 | 0.9760\n\n**Q3: Rely on a specific data distribution or dataset size.**\nIn terms of dataset size, our method has been validated on multiple large-scale datasets, including ImageNet100, ImageNet1K, and Glint360k. These datasets encompass a wide range of category sizes, ranging from 100 to 360k, and sample numbers ranging from 10k to 17 million, respectively. It is noteworthy that the Glint360k dataset utilized in our experiments is currently the largest dataset verified amongst all deep hashing methods, to the best of our knowledge. In terms of data distribution, the datasets used in our experiments consist of both face datasets and general object recognition dataset. Additional validation on even larger datasets, such as ImageNet21k and webface260k, will be left for our future work.\n\n"}, {"review_id": "gYy5ryDj4l", "reviewer": "Reviewer_WmwN", "summary": "This paper presents a novel deep hashing framework based on product quantization. It is different from conventional PQ in learning a set of predefined PQ codes of the classes via a softmax-based differentiable PQ branch. The proposed method is validated to be effective on large scale datasets, including Glint360k.", "questions": "In Fig. 2, the results for the proposed method are only shown for PQ 32 onwards. How about the results with PQ64, PQ128 and PQ256?", "limitations": "No. One limitation may be the setting of class-level PQ labels, which relies on a pre-trained model.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper tackles the hashing for large scale datasets with millions of categories and hundreds of millions of samples, which may extend the range that hashing methods can be applied for.\n\nThe codebook is learned via PQ branch rather than clustering with the predefined class-level PQ labels as supervision.\n\nThe proposed method can be used for retrieval as the traditional PQ but with a low-slope decay of retrieval performance with decreasing code lengths.\n\nThe proposed method is validated on large scale datasets to be effective.", "weaknesses": "While the overall idea and implementation is simple, there are some implementation or adaptation details not clearly clarified. This includes the PQ code duplication removal in Sec. 4.2. There are also some adaptations when applying the method on the ImageNet100 and ImageNet1K datasets, for example using instance-level features and use OrthoHash to generate PQ labels. It is better to clearly specify the scenarios for different settings to avoid misunderstanding.\n\nWhile the method section describes both symmetric and asymmetric retrieval, only the asymmetric results are reported.\n\nLine 277, 'atrong' -> 'strong'. Line 284, 'we' -> 'We'.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Further detail.** \n\nThank you for your suggestion, now we provide further detail, and they will all be added to the supplementary material later.\n\n**PQ code duplication removal.** We provide further explanations here.  For the sake of clarity, if we need to modify $n$ items of PQ codes to achieve deduplication, we refer to it as \"**n-replace**.\" Initially, we perform product quantization training on class average features to obtain PQ codes for each class, with each PQ code consisting of $M$ segments. In addressing a recurring PQ code $P$,  we begin first attempt \"1-replace.\" For every sub-vector $F_m$ associated with $P_m$, we compute its distance to the $K$ cluster centers of the m-th sub-codebook. This computation yields a total of $M \\times K$ distances. We then proceed sequentially, seeking to substitute the PQ code with the index of the nearest cluster center, thereby achieving deduplication. If none of the $M \\times K$ possibilities allow for substitution, we progress to the \"2-replace\".  First, we forcibly apply the \"1-replace\" to substitute the PQ segment with the index $k^*$ of the nearest m-th sub-codebook, and we maintain this alteration. Following this, we iteratively apply the \"1-replace\"  based on this condition. This iterative procedure is reiterated until a non-recurring PQ code is detected. In simple terms, we aim to find a replaceable PQ code with minimal item changes for repeated PQ codes while minimizing the quantization error as much as possible.\n\n**Instance-level features to generate PQ labels.** Here, \"instance\" represents the sigle sample's features, not the class average features. In this setting, to avoid having insufficient samples for PQ cluster training, we utilize the instance-level features to train the PQ algorithm and obtain the codebook of PQ. This codebook will be used for encoding the class average features.\n\n**PQ label generation in OrthoHash's approach.** OrthoHash hope to generate hash codes with a maximally expansive Hamming distance interval. This is achieved through a process of repetitive Bernoulli sampling. If a sampled hash code is found to be in proximity to the Hamming distance of a previously collected sample, it is discarded and the sampling is repeated. Subsequent to the generation of hash codes using the OrthoHash's Approach, we divide it into $M$ segments and transform them into PQ codes. \n\n\n**Q2: Asymmetric results.**\n\nWe conducted experiments on symmetric retrieval, and as shown in the table below, our method still achieved excellent performance. We observed comparable retrieval performance among PQ4, PQ8, and PQ16, and the increase in code length does not have a positive impact on symmetric retrieval performance. We think this can be attributed to the heightened noise in symmetric retrieval resulting from the expansion of the number of PQ code segments.\n\n|||Glint360k iResnet100||\n:----:|:----:|:----:|:----:\n||PQ4 |PQ8| PQ16\nTop-1 | 0.9387 | 0.9343 | 0.9341\nTop-5 | 0.9625 | 0.9609 | 0.9492\nTop-20 | 0.9647 | 0.9649 | 0.9565\n\n\nWe also conducted experiments using different backbones, and the results are as follows. It can be observed that, similar to asymmetric retrieval, as the complexity of the model increases, the performance improves.\n\n\n||iResnet100 |iResnet50 | iResnet18|\n:----:|:----:|:----:|:----:\n||PQ4 |PQ4| PQ4\nTop-1 | 0.9387 | 0.9263 | 0.6175\nTop-5 | 0.9625 | 0.9441 | 0.6524\nTop-20 | 0.9647 | 0.9489 | 0.6868\n\n**Q3: Minor sentence error.**\n\nThanks for pointing it out. We will correct it and review the paper carefully.\n\n"}, {"review_id": "lqHgvthyA2", "reviewer": "Reviewer_AU32", "summary": "In this paper, a framework for large-scale image retrieval is proposed, which is based on deep hashing and product quantization (PQ). The key contribution of this framework is the alleviation of the performance crash problem that arises when using very short PQ codes to save space and computation. The performance of the proposed method is demonstrated through experiments conducted on multiple large-scale datasets with numerous classes.", "questions": "Line 116 of Page 3: It is not clear whether \"N\"/\"2^b\" refers to \"the class number of the dataset\"/\"256\" based on the previous explanation (Line 113-115). Additionally, it should be noted that \"N\" is used to represent the batch size in Equation 2.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper is well-organized and provides clear introductions to the details.\n2.\tIt explains the potential reasons behind the performance decline of short PQ codes and supports its claims through extensive experiments.\n3.\tThe proposed method is both novel and potentially practical, alleviating the problems of saving space and time in large-scale image retrieval.", "weaknesses": "1.\tSeveral specific experiments, such as \"different network structures,\" \"visualization of sub-features and clustering centers,\" and \"compression efficiency,\" are conducted using the proposed method and traditional PQ alone. However, this comparison may be unfair as it overlooks other outstanding methods.\n2.\tAs the key contribution, it is important to provide a thorough comparison of the performance decline or crack between the proposed PQ method and other outstanding PQ-based methods when using shorter PQ codes.\n3.\tVisual retrieval samples of Top-K should be provided for clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: More results.**\n\n**Different network structures.** Thank you. Because of the limited time, we have supplemented the results of two outstanding methods, OrthoHash and GreedyHash, which have shown relatively good performance on iResnet50 in our paper. Specifically, we evaluated their performance on iResnet18 and iResnet100 as well (the experiment of OrthoHash with 64-bit on iResnet100 is still in progress, and we will provide the results later). The performance comparison is tabulated below. As can be observed, in comparison to these two excellent methods, our approach equally demonstrates substantial performance gains. Furthermore, all techniques exhibit performance improvements with an increase in network capabilities.\n.\n|     |     |      |     |iR18||||||\n|:---:|---:|:---:|:---|---:|:---:|:---|---:|:---:|:---|\nMethod ||32 bits||| 64 bits |||128 bits\n||Top-1| Top-5| Top-20 |Top-1 |Top-5| Top-20 |Top-1 |Top-5 |Top-20\nPQ  |     0.0973  |     0.1940  |     0.3031 |      0.4588 |      0.5958  |     0.6903  |     0.8005  |     0.8659  |     0.9025\nOrthoHash |      0.0384 |      0.0528 |      0.0650 |      0.0960  |     0.1206 |      0.1421 |      0.2024  |     0.2426  |     0.2749\nGreedyHash |      0.0991 |      0.1921 |      0.3014 |      0.4003 |      0.5507  |     0.6620 |      0.7344  |     0.8290 |     0.8824\nOurs |      **0.6945** |      **0.7576** |      **0.8006** |      **0.7019** |      **0.7890** |      **0.8414** |      **0.8231** |      **0.8824**  |     **0.9133**\n\n\n\n|     |     |      |     |iR100||||||\n|:---:|---:|:---:|:---|---:|:---:|:---|---:|:---:|:---|\nMethod ||32 bits||| 64 bits |||128 bits\n||Top-1| Top-5| Top-20 |Top-1 |Top-5| Top-20 |Top-1 |Top-5 |Top-20\nPQ | 0.2074 |0.3569 |0.4941 |0.7380| 0.8378 |0.8878 |0.9465 |0.9658 |0.9720\nOrthoHash | 0.4904 |0.5511 |0.5953 |- |- |- |0.7804| 0.8185 |0.8444\nGreedyHash | 0.5902       |0.7271 |0.8035 |0.7475\t|0.8381\t|0.8861\t| 0.8529\t| 0.9135\t |0.9415\nOurs |**0.9305** | **0.9700**       |**0.9734** |**0.9578** |**0.9728** |**0.9753** |**0.9679**| **0.9746** |**0.9772**\n\n\n**Visualization of sub-features and clustering centers.** Other binary deep hashing methods lack the incorporation of sub-features and sub-clustering centers. Additionally, executing PQ-based deep hashing methods on the Glint360k dataset presents challenges, including convergence issues in methods like DPQ([23]) and computational complexity concerns in OPQN([49]), ADSVQ([51]), and DCDH([48]),  and others. Consequently, we solely visualizing and comparing the results between PQ and our proposed method.\n\n**Compression efficiency.** On the iResnet50 architecture, we provide a comprehensive visual comparison in Figure 2.\n\n**Q2. Comparison of the performance decline.**  \n\nThank you. The original paper's Table 1 illustrates the decline in performance of other deep hashing methods. Particularly, when using longer codes like 128 bits, these methods already face difficulties and exhibit lower retrieval performance in large-scale datasets. Moreover, they show a substantial decline in performance as the code length becomes shorter. For instance, OrthoHash's Top-1 accuracy decreases from 0.6626 at 128 bits to 0.5526 at 64 bits and further drops to 0.3098 at 32 bits. Similarly, GreedyHash's Top-1 accuracy decreases from 0.8259 at 128 bits to 0.6102 at 64 bits and further diminishes to 0.3688 at 32 bits.  More lucid visualization can be find in Figure 2(provided in pdf).\n\n\n**Q3. Top-K visualization.**\n\nThank you for your suggestion. In Figure 1(provided in pdf), we present visualizations of the Top-20 retrieval results on the Megaface and Facecrub datasets. This encompasses comparisons between various ways: 1) our method, which includes L2 retrieval and PQ4 retrieval (without feature processing, normalization, or segment normalization), and 2) the original L2 retrieval and naive PQ4 retrieval (with or without feature normalization). It can be observed that our method generates similar top-20 results under different feature preprocessing settings, further validating the insensitivity of our method to feature preprocessing.  Additionally, due to the introduced noise from quantization, we can observe a low overlap rate of Top-20 results between the PQ4 retrieval result and the L2 retrieval result."}, {"review_id": "qSFQlCUOcl", "reviewer": "Reviewer_hk7b", "summary": "This paper presents a deep product quantization (PQ) method for approximate nearest neighbor (ANN) search. The motivation is to reduce performance degradation when short codes are applied to large-scale datasets with a large number of categories. The proposed method learns discriminative PQ subvectors by CosFace loss with pseudo-ground truth labels obtained by applying PQ to the set of mean vectors of all the classes. Experiments on Glint360K and ImageNet datasets show that the proposed method yields highly competitive or better performance than several existing ANN methods.", "questions": "I hope the authors will resolve all the ambiguities I listed in A1-A6.", "limitations": "I could not find any discussion of the limitations of the proposed method. It might be a good idea to discuss the performance if there exist distribution shifts among the training, gallery, and probe sets.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "Table 1 shows that when using 32-bit codes for the Glint360k dataset with a large number of categories, the performance of existing ANN methods is poor, and the proposed method has a significant advantage. \n\nThe proposed method achieves the same or better accuracy as the existing methods even for ImageNet with a small number of categories.", "weaknesses": "A. Due to several ambiguities, I could not understand some important details about the experiment and wondered if the evaluation was done in a fair manner. Specific examples are listed below.\n\nA1. Reading Section 5.1 I assume that Glint360K is used only for training and Mageface and Facecrub are used for testing. However, I find an explanation in line 260, \"We will assess the retrieval performance using top-1, top-5, and top-20 accuracies on the Glint360K datasets,\" which is contradictory.\n\nA2. Related to the above point, line 221 says that \"for each individual, we have M images. We will test each image by incorporating it into the gallery of distractors and employing each of the other M-1 images as a probe.” Is there any reason to use such a tricky protocol? If the gallery and probe sets are Megaface and Facecrub, respectively, then both should contain images of the same individuals. So I don't see why they need to add images of Facecrub to Megaface. It seems to me that there is a concern that this protocol could introduce a dataset bias to some extent into the evaluation.\n\n\nA3. I assume the \"both datasets\" in line 230 refers to Celeb-500k and MS1M-Retinaface, which comprise Glint360K, but it is hard to understand because there is no specific reference to them.\n\n\nA4. Reading line 239, it appears that the same learning conditions are applied to all the methods. However, the appropriate learning conditions are generally different for different methods and have a significant impact on their accuracy, so I was concerned that this comparison is really fair.\n\n\nA5. Is the feature preprocessing also applied to the baselines to be compared? Even if the performance of the proposed method does not change with or without preprocessing, the performance of the baseline to be compared may not. For fairness, comparisons with normalized features should also be reported.\n\n\nA6. Sections 5.2 and 5.2.1 each describe learning conditions, and some of them, such as the learning rate, appear to be contradictory. Further clarification would be needed.\n\n\nB. Some additional evaluations should be conducted to clarify the effectiveness of the proposed method. \n\nB1. Looking at the ImageNet results (Tables 3 and 4) and the Glint360K results (Tables 1 and 2), the trend of the performance gap is very different. What causes the performance gap should be clarified. Specifically, although the proposed method does not always provide significant improvement over the baselines on ImageNet, it shows significant advantages on Glint360K when shorter codes are used, suggesting that the number of classes has a significant impact on the performance gap. If this is true, it should be interesting to analyze the performance gap for various number of classes.\n\n\nB2. Another simple baseline to be compared would be a straightforward combination of fine-tuned feature extraction backbone + supervised quantization, i.e., first extract a deep feature of an image by using feature extraction backbone fine-tuned with a training data (e.g., Glint360K), and then use supervised quantization (e.g., [Wang et al., Supervised Quantization for Similarity Search, ICCV2016]) to encode the feature into a short code. Comparison to such an approach may clarify the effectiveness of the proposed method further. \n\n\nC. The proposed method is not very novel, since many deep product quantization methods have been proposed in the past (e.g., [23, 28, 45, 49, 50] or [Jang et al., Generalized Product Quantization Network for Semi-supervised Image Retrieval, CVPR2020]).\n\n\nD. Some minor problems\n\nD1. How is the <||F_m||, C_mk> in Equation (9) is computed?\n\nD2. The number of categories is large enough compared to previous standards in ANN searches, but the sample size assumed in this paper does not seem very appealing given that public datasets with 1B-scale samples (such as GIST1B) have been used since the early years.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. Retrieval performance.**\n\nWe evaluate the unseen retrieval performance on the Glint360k dataset: Glint360k is exclusively used for training, while Mageface and Facecrub are employed for testing. \n\n**Q2. Evaluation protocol.**\n\nIn fact, the protocol we described is widely recognized and implemented across various studies. For more specific details, we would recommend referring to  [Kemelmacher-Shlizerman, Ira, et al. \"The megaface benchmark: 1 million faces for recognition at scale.\" CVPR 2016].\n\n**Q3. \"Both datasets\".**\n\nThank you very much for pointing out the issues in line 203. Indeed, as you mentioned, \"both datasets\"  refers to the clean Celeb-500k and MS1M-Retinaface datasets. We will make the necessary corrections accordingly..\n\n**Q4. Same learning conditions.** \n\nIn fact, for these methods, we utilized the default settings provided by the Cisip project, if available, or relied on the publicly accessible projects provided by the original authors. Considering that these methods may not provide specific learning rate strategies for the datasets we test, it would be unfeasible to perform grid search or other methods to find the optimal learning rate strategy for the numerous methods we compared. On the other hand, these methods mostly are based on fine-tuning, using the default settings, such as an initial learning rate of 0.0001 and decreased to 0.00001, may not have a disruptive impact on the conclusions drawn.\n\n**Q5. Feature preprocessing.** \n\nFor other methods, we incorporate their specific feature preprocessing techniques as defined by the respective authors. This includes applying feature normalization, which often results in improved performance, if the methods recommend or require it.\n\n\n**Q6. Learning rate contradictory.**\n\nSection 5.2.1 provides further details compared to Section 5.2. On the Glint360k dataset, the setup is as follows: as stated in the papers of the deep hashing methods we compare against, they utilize pretrained models to initialize network parameters and perform fine-tuning. As a result, these methods set their initial learning rate to 0.0001. However, our approach conducts training from scratch, utilizing only the PQ label provided by the pre-trained model. Therefore, our initial learning rate is set to 0.1. \n\n\n**Q7. Performance comparison on various number of classes.**\n\nThank you. This is indeed an interesting issue. To assess the performance variations across different numbers of classes, we conducted the following experiment: we selected training data from Glint360k, which included the first 3k, 5k, 10k, 72,046 (20% of the total class number), 180,116 (50%), and 360,232 (100%) classes. It is crucial to highlight that in previous setting, we conducted unseen retrieval on Glint360k using Megaface and Facecrub datasets. Recognizing that the reduced diversity of training data may impact the performance of unseen retrieval, we conducted tests on the first 20W images from the Glint360k dataset to evaluate the learning performance of various methods. From each class, we extracted one image to construct the query set, totaling 2862 images, while the remaining data served as the gallery set. We provided the performance results for Top1 and Top20 in the Tabel 1(provided in pdf).\nWe can observe that as the number of classes increases, OrthoHash gradually weakens its ability. GreedyHash achieves it's optimal performance when the number of classes is small. Our method consistently achieves high performance.  For greater clarity, we more provide a trend visualization in Figure 3(provided in pdf).\n\n\n\n**Q8. Another baseline.**\n\nThanks you for your suggestion. Similar to PQ, SQ is also a non-deep hashing method. It aims to learn a transformation matrix that maps features into a discriminative subspace and utilizes CQ ([50]) for retrieval. However, as the source code for SQ is not available, we cannot guarantee an accurate reproduction within a limited timeframe. We will try to include this baseline in the future.\n\n\n**Q9. The difference with other deep product quantization methods.**\n\nAs one of the most popular methods for quantization retrieval, there are indeed have many techniques aiming to improve the retrieval performance of PQ. However, it is worth noting that our method stands out by extending the applicability of deep hashing methods to large-scale datasets, which sets it apart from other methods. Moreover, in terms of methodology, our approach exhibits significant differences compared to others. DPQ ([23]) achieves self-learning of PQ codes by classifying the soft quantized features and employing two regularization terms. GPQ[Jang et al., Generalized Product Quantization Network for Semi-supervised Image Retrieval, CVPR2020] is similar to DPQ as it classifies soft quantized features and utilizes a metric learning strategy within subvectors. Similarly, PQN ([45]) constructs soft quantized features and learns based on triplet loss. PQM ([28]) utilizing quantized features for classification and optimizing quantization error through iterative updates. In comparison, our approach focuses on subspaces. For OPQN ([49]), it's codebook is predefined and limited by the feature dimensionality. CQ ([50]) is a non-deep feature quantization method.\n\n**Q10. How is the <||F_m||, C_mk> in Equation (9) is computed.**\n\nF_m represents the normalized result of the m-th sub-feature. C_mk refers to the k-th item of the m-th sub-codebook, where ||C_mk|| = 1. <•> can either be the cosine distance or the Euclidean distance. As the C_mk has constant feature norm, for F_m, regardless of whether or not the normalization is applyed, it always finds the same closest C_mk, in other words, assigned to same C_mk, denoted as C_mk*.\n\n**Q11. About GIST1B**\n\nGIST1B is a fixed feature representation set that cannot be learned. For deep hashing methods, they require adaptive learning to the features. Therefore, deep hashing methods usually do not include benchmark comparisons on GIST1B. "}]

Author rebuttal:
We thank all reviewers for their valuable comments. Reviewers kMZn, WmwN, and AU32 have mentioned that the method proposed in this paper is novel(new) and have affirmed its potential applicability. Reviewers hk7b also acknowledged the contributions of our method.

The PDF file contains Figure 1, Figure 2, Figure 3, and Table 1.

Moving forward, we will address the questions raised by the reviewers point by point.

Meta-review: Overall, this paper presents a novel approach to address the challenges of applying deep hashing to large-scale datasets, specifically focusing on product quantization (PQ) as a key component. The proposed method offers several strengths, such as its ease of implementation, scalability to large-scale datasets with millions of categories and samples, and its potential practicality for space and time-efficient large-scale image retrieval. All the reviewers unanimously agree that the paper presents a strong contribution in the field of deep hashing over large-scale datasets. To strengthen the paper for publication, the authors should provide greater clarity on implementation details, and expand their comparison with the existing methods using shorter PQ codes. Additionally, including visual retrieval samples would further enhance the paper's comprehensibility. In summary, this paper is well-received by all the reviewers and can be accepted with minor revisions to address the mentioned concerns.
Decision: Accept (poster)