Cartesian K-Means

By Mohammad Norouzi, David J. Fleet. 2013

332 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, Media Technology, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Media Technology

In Representation & Self-Supervised Learning

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “Our paper focuses on methods based on product quantization (PQ) codes, as these were shown to be more eﬀective than binary codes [34].”
Efficient Natural Language Response Suggestion for Smart Reply (2017, methodology): “We use a learned rotation before product quantization as it has been shown to improve quantization error [16].”
FastText.zip: Compressing text classification models (2016, background): “The original PQ has been concurrently improved by Ge et al. (2013) and Norouzi & Fleet (2013), who learn an orthogonal transform minimizing the overall quantization loss.”
Compressing Deep Convolutional Networks using Vector Quantization (2014, methodology): “Many learning-based binarization or product quantization methods are available, such as Spectral Hashing (Weiss et al., 2008), Iterative Quantization (Gong et al., 2012), and Catesian k means (Norouzi & Fleet, 2013), among others.”
Fast Decoding in Sequence Models using Discrete Latent Variables (2018, methodology): “The approach of sliced Vector Quantization has also been studied more recently in the context of clustering, under the name of Product or Cartesian Quantization in (Jegou et al., 2011; Norouzi & Fleet, 2013).”
Image Classification and Retrieval are ONE (2015, methodology): “Improvements of PQ include Cartesian K -Means [35] and Composite Quantization [69].”
A Survey on Learning to Hash (2016, methodology): “BRE = binary reconstructive embedding [66], MLH = minimal loss hashing [107], LSH = locality sensitive hashing [14], ITQ = iterative quantization [35], [36], SH = spectral hashing [156], AGH-2 = two-layer hashing with graphs [86], USPLH = unsupervised sequential projection learning hashing [143], PQ”
Optimized Product Quantization for Approximate Nearest Neighbor Search (2013, result): “Concurrent with our work, a very similar idea is independently developed by Norouzi and Fleet [14].”
Theory and Experiments on Vector Quantized Autoencoders (2018, result): “on. However, additional training heuristics, namely, exponential Equal contribution arXiv:1805.11063v1 [cs.LG] 28 May 2018 moving averages (EMA) of cluster assignment counts, and product quantization [22] were essential to achieve competitive results with VQ-VAE. In this work, we show that tuning fo”
Learning Binary Codes for Maximum Inner Product Search (2015, background): “Besides hashing, vector quantization (VQ) [2, 6, 10, 27, 40, 41] is another promising direction for large-scale search problems in high-dimensional space.”
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search (2014, methodology): “Optimization per cell is discussed in section 4.2, mostly following [9, 15]; the same process is used in section 4.4, discussing LOPQ in the multi-index case.”
Improving Bilayer Product Quantization for Billion-Scale Approximate Nearest Neighbors in High Dimensions (2014, methodology): “As a side note, it was shown in [4, 6] that the accuracy of the PQ compression considerably outperforms binary hashing methods for the same compression rates.”
Optimized Cartesian K-Means (2014, methodology): “C V ] 16 M ay 2 01 4 Index Terms—Clustering, Cartesian product, Nearest neighbor search ✦”
Hashing for Distributed Data (2015, methodology): “On the i-th node, there is a local set of ni data points, denoted in matrix form as Xi ∈ Rd×ni , whose columns are data points.”
24/7 Place Recognition by View Synthesis (2018, unknown): “descriptors using product quantization (PQ) [21], [56], [57].”
Binary Generative Adversarial Networks for Image Retrieval (2017, methodology): “Recently, learning-based hashing methods [16, 17, 27, 34, 43, 45] have become the mainstream for scalable image retrieval due to their compact binary representation and efﬁcient Hamming distance 1 Our anonymous code is available at: https://github.com/htconquer/BGAN Permission to make digital or…”
The Inverted Multi-Index (2012, methodology): “First, Ge et al. [27] have improved the accuracy of the search by replacing the product quantization with the optimized product quantization (OPQ) [28], [29].”
And the Bit Goes Down: Revisiting the Quantization of Neural Networks (2019, background): “Vector Quantization (VQ) and Product Quantization (PQ) have been extensively studied in the context of nearest-neighbor search [30, 31, 32].”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “This differs from prior work in that it (a) identifies and addresses the problem of variance in data point norms; (b) includes coarse quantizers as a part of the optimization; and (c) is endto-end trainable using stochastic gradient descent (SGD), which leads to a significant improvement in quantiza”