Algorithm 1 The algorithm to adaptively leamn the thresh- r will be 1%,0.01%,and 10-16,respectively.Much less en- olds for DBO. tries will gain higher collision probability (improve recall). Input:The whole point set S faster query speed and less storage.In fact,the number of Initialize with possible entries of c bits of DBQ code only equals to that of S1←{xl-oo<x≤0，x∈S} 0.79c bits of ordinary SBQ or HH code. S2←-0 S3←{xl0<x<+o,x∈S} Experiment max←0 sort the points in S Data Sets sort the points in Sa We evaluate our methods on two widely used data sets, while S1≠0orS3≠0do CIFAR (Krizhevsky 2009)and LabelMe (Torralba,Fergus, if sum(S2)≤0then and Weiss 2008). move the smallest point in S3 to S2 The CIFAR data set (Krizhevsky 2009)includes different else versions.The version we use is ClFAR-10,which consists of move the largest point in S to S2 60,000 images.These images are manually labeled into 10 end if classes,which are airplane,automobile,bird,cat,deer,dog. compute F frog,horse,ship,and truck.The size of each image is 32x32 if F>max then pixels.We represent them with 512-dimensional gray-scale set a to be the largest point in S1,and b to be the GIST descriptors(Oliva and Torralba 2001). largest point in S2 The second data set is 22K LabelMe used in (Torralba, max←-F Fergus,and Weiss 2008:Norouzi and Fleet 2011).It con- end if sists of 22,019 images.We represent each image with 512- end while dimensional GIST descriptors(Oliva and Torralba 2001). Evaluation Protocols and Baseline Methods Figure 1(c)to quantize the points in these subsets into 01, As the protocols widely used in recent papers (Weiss, 00,10,respectively. Torralba,and Fergus 2008;Raginsky and Lazebnik 2009; Gong and Lazebnik 2011),Euclidean neighbors in the orig- Discussion inal space are considered as ground truth.More specifi- cally,a threshold of the average distance to the 50th nearest Let us analyze the expected performance of our DBQ.The neighbor is used to define whether a point is a true positive first advantage of DBQ is about accuracy.From Figure 1 or not.Based on the Euclidean ground truth,we compute and the corresponding analysis,it is expected that DBQ will the precision-recall curve and the mean average precision achieve better accuracy than SBQ and HH because DBQ can (mAP)(Liu et al.2011;Gong and Lazebnik 2011).For all better preserve the similarity relationships between points. experiments,we randomly select 1000 points as queries,and This will be verified by our experimental results. leave the rest as training set to learn the hash functions.All The second advantage of DBQ is on time complexity,in- the experimental results are averaged over 10 random train- cluding both coding(training)time and query time.For a c- ing/test partitions. bit DBQ,we only need to generate c/2 projected dimensions Our DBQ can be used to replace the SBQ stage for any while SBQ need c projected dimensions.For most meth- existing hashing method to get a new version.In this paper, ods,the projection step is the most time-consuming step. we just select the most representative methods for evalua- Although some extra cost is needed to adaptively learn the tion,which contain SH(Weiss.Torralba.and Fergus 2008) thresholds for DBQ,this extra computation is just sorting PCA (Gong and Lazebnik 2011),ITQ(Gong and Lazebnik and an one-time scan of the training points which are actu- 2011),LSH (Andoni and Indyk 2008),and SIKH (Raginsky ally very fast.Hence,to get the same size of code,the over- and Lazebnik 2009).SH,PCA,and ITQ are data-dependent all coding time complexity of DBQ will be lower than SBQ. methods,while LSH and SIKH are data-independent meth- which will also be verified in our experiment. ods.By adopting different quantization methods,we can As for the query time,similar to coding time,the num- get different versions of a specific hashing method.Let's ber of projection operations for DBQ is only half of that for take SH as an example."SH-SBQ"denotes the original SH SBQ.Hence,it is expected that the query speed of DBQ will method based on single-bit quantization,"SH-HH"denotes be faster than SBQ.The query time of DBQ is similar to that the combination of SH projection with HH quantization(Liu of HH because HH also uses half of the number of projection et al.2011),and"SH-DBQ"denotes the method combining operations for SBQ.Furthermore,if we use inverted index the SH projection with double-bit quantization.Please note or hash table to accelerate searching,ordinary c-bit SBQ or that threshold optimization techniques in (Liu et al.2011) HH coding would have 2e possible entries in the hash table. for the two non-zero thresholds in HH can not be used for As DBQ does not allow code'11',the possible number of the above five methods.In our experiments,we just use the entries for DBQ is 3/2.This difference is actually very sig- same thresholds as those in DBO.For all the evaluated meth- nificant.Let r denote the ratio between the number of entries ods,we use the source codes provided by the authors.For for DBQ and that for SBQ (or HH).When c=32,64,256, ITQ,we set the iteration number to be 100.To run SIKH,weAlgorithm 1 The algorithm to adaptively learn the thresh￾olds for DBQ. Input: The whole point set S Initialize with S1 ← {x| − ∞ < x ≤ 0, x ∈ S} S2 ← ∅ S3 ← {x|0 < x < +∞, x ∈ S} max ← 0 sort the points in S1 sort the points in S3 while S1 6= ∅ or S3 6= ∅ do if sum(S2) ≤ 0 then move the smallest point in S3 to S2 else move the largest point in S1 to S2 end if compute F if F > max then set a to be the largest point in S1, and b to be the largest point in S2 max ← F end if end while Figure 1(c) to quantize the points in these subsets into 01, 00, 10, respectively. Discussion Let us analyze the expected performance of our DBQ. The first advantage of DBQ is about accuracy. From Figure 1 and the corresponding analysis, it is expected that DBQ will achieve better accuracy than SBQ and HH because DBQ can better preserve the similarity relationships between points. This will be verified by our experimental results. The second advantage of DBQ is on time complexity, in￾cluding both coding (training) time and query time. For a c￾bit DBQ, we only need to generate c/2 projected dimensions while SBQ need c projected dimensions. For most meth￾ods, the projection step is the most time-consuming step. Although some extra cost is needed to adaptively learn the thresholds for DBQ, this extra computation is just sorting and an one-time scan of the training points which are actu￾ally very fast. Hence, to get the same size of code, the over￾all coding time complexity of DBQ will be lower than SBQ, which will also be verified in our experiment. As for the query time, similar to coding time, the num￾ber of projection operations for DBQ is only half of that for SBQ. Hence, it is expected that the query speed of DBQ will be faster than SBQ. The query time of DBQ is similar to that of HH because HH also uses half of the number of projection operations for SBQ. Furthermore, if we use inverted index or hash table to accelerate searching, ordinary c-bit SBQ or HH coding would have 2 c possible entries in the hash table. As DBQ does not allow code ‘11’, the possible number of entries for DBQ is 3 c/2 . This difference is actually very sig￾nificant. Let r denote the ratio between the number of entries for DBQ and that for SBQ (or HH). When c = 32, 64, 256, r will be 1%, 0.01%, and 10−16, respectively. Much less en￾tries will gain higher collision probability (improve recall), faster query speed and less storage. In fact, the number of possible entries of c bits of DBQ code only equals to that of c log2 3 2 ≈ 0.79c bits of ordinary SBQ or HH code. Experiment Data Sets We evaluate our methods on two widely used data sets, CIFAR (Krizhevsky 2009) and LabelMe (Torralba, Fergus, and Weiss 2008). The CIFAR data set (Krizhevsky 2009) includes different versions. The version we use is CIFAR-10, which consists of 60,000 images. These images are manually labeled into 10 classes, which are airplane, automobile, bird, cat, deer, dog, frog, horse, ship, and truck. The size of each image is 32×32 pixels. We represent them with 512-dimensional gray-scale GIST descriptors (Oliva and Torralba 2001). The second data set is 22K LabelMe used in (Torralba, Fergus, and Weiss 2008; Norouzi and Fleet 2011). It con￾sists of 22,019 images. We represent each image with 512- dimensional GIST descriptors (Oliva and Torralba 2001). Evaluation Protocols and Baseline Methods As the protocols widely used in recent papers (Weiss, Torralba, and Fergus 2008; Raginsky and Lazebnik 2009; Gong and Lazebnik 2011), Euclidean neighbors in the orig￾inal space are considered as ground truth. More specifi- cally, a threshold of the average distance to the 50th nearest neighbor is used to define whether a point is a true positive or not. Based on the Euclidean ground truth, we compute the precision-recall curve and the mean average precision (mAP) (Liu et al. 2011; Gong and Lazebnik 2011). For all experiments, we randomly select 1000 points as queries, and leave the rest as training set to learn the hash functions. All the experimental results are averaged over 10 random train￾ing/test partitions. Our DBQ can be used to replace the SBQ stage for any existing hashing method to get a new version. In this paper, we just select the most representative methods for evalua￾tion, which contain SH (Weiss, Torralba, and Fergus 2008), PCA (Gong and Lazebnik 2011), ITQ (Gong and Lazebnik 2011), LSH (Andoni and Indyk 2008), and SIKH (Raginsky and Lazebnik 2009). SH, PCA, and ITQ are data-dependent methods, while LSH and SIKH are data-independent meth￾ods. By adopting different quantization methods, we can get different versions of a specific hashing method. Let’s take SH as an example. “SH-SBQ” denotes the original SH method based on single-bit quantization, “SH-HH” denotes the combination of SH projection with HH quantization (Liu et al. 2011), and “SH-DBQ” denotes the method combining the SH projection with double-bit quantization. Please note that threshold optimization techniques in (Liu et al. 2011) for the two non-zero thresholds in HH can not be used for the above five methods. In our experiments, we just use the same thresholds as those in DBQ. For all the evaluated meth￾ods, we use the source codes provided by the authors. For ITQ, we set the iteration number to be 100. To run SIKH, we