Composite Quantization for Approximate Nearest Neighbor Search
Authors: Ting Zhang, Chao Du, Jingdong Wang
ICML 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform the ANN experiments on five datasets: MNIST (Le Cun et al., 2001), 784D grayscale images of handwritten digits; Label Me22K (Russell et al., 2008) a corpus of images expressed as 512D GIST descriptors; 1M SIFT (J egou et al., 2011a), consisting of 1M 128D SIFT features as base vectors, 100K learning vectors and 10K queries; 1M GIST (J egou et al., 2011a), containing 1M 960D global GIST descriptors as base vectors, 500K learning vectors and 1K queries; and 1B SIFT (J egou et al., 2011b), composed of 1B SIFT features as base vectors, 100M learning vectors and 10K queries. The detailed description is presented in Table 1. We compare our approach, composite quantization (CQ), with several state-of-the-art methods: product quantization (PQ) (J egou et al., 2011a), Cartesian k-means (CKM) (Norouzi & Fleet, 2013). It is already shown that PQ and CKM achieve better search accuracy than hashing algorithms with the same code length and comparable search efficiency. Thus, we report one result from a representative hashing algorithm, iterative quantization (ITQ) (Gong & Lazebnik, 2011). The search quality is measured using recall@R. |
| Researcher Affiliation | Collaboration | Ting Zhang ZTING@MAIL.USTC.EDU.CN University of Science and Technology of China, Hefei, P.R. China Chao Du DUCHAO0726@GMAIL.COM Tsinghua University, Beijing, P.R. China Jingdong Wang JINGDW@MICROSOFT.COM Microsoft Research, Beijing, P.R. China |
| Pseudocode | No | The paper describes the algorithm in Section 3.1 but does not present it in a structured pseudocode block or a clearly labeled algorithm figure. |
| Open Source Code | No | The paper refers to a 'publicly available implementation of L-BFGS' but does not provide any statement or link for the source code of their proposed method. |
| Open Datasets | Yes | We perform the ANN experiments on five datasets: MNIST (Le Cun et al., 2001), 784D grayscale images of handwritten digits; Label Me22K (Russell et al., 2008) a corpus of images expressed as 512D GIST descriptors; 1M SIFT (J egou et al., 2011a), consisting of 1M 128D SIFT features as base vectors, 100K learning vectors and 10K queries; 1M GIST (J egou et al., 2011a), containing 1M 960D global GIST descriptors as base vectors, 500K learning vectors and 1K queries; and 1B SIFT (J egou et al., 2011b), composed of 1B SIFT features as base vectors, 100M learning vectors and 10K queries. The detailed description is presented in Table 1. |
| Dataset Splits | Yes | The validation dataset is a subset of the database (selecting a subset is only for validation efficiency, and it is fine that the validation set is a subset of the learning set as the validation criterion is not the objective function value but the search performance). |
| Hardware Specification | No | The paper does not provide specific details about the hardware (e.g., CPU, GPU models, or memory) used for running the experiments. |
| Software Dependencies | No | The paper mentions using the 'L-BFGS algorithm' and links to a public implementation, but it does not specify version numbers for any other software dependencies or libraries used in the experiments. |
| Experiment Setup | Yes | We choose K = 256 as the dictionary size... It takes O(MKd Tb) with Tb being the number of iterations (= 3 in our implementation achieving satisfactory results)... The time complexity for updating {Cm} is O(NMd Tl Tc) with Tc being the number of iterations (= 10 in our implementation) and Tl (set to 5 in our implementation) being the number of line searches in L-BFGS. Therefore, our algorithm instead relaxes this constraint and selects the parameter µ via validation. |