Optimized Cartesian K-Means

By Jianfeng Wang, Jingdong Wang, Jingkuan Song, Xin-Shun Xu, Heng Tao Shen, Shipeng Li. 2014

121 citations recorded by the source corpus.

Product quantization-based approaches are effective to encode high-dimensional data points for approximate nearest neighbor search. The space is decomposed into a Cartesian product of low-dimensional subspaces, each of which generates a sub codebook. Data points are encoded as compact binary codes using these sub codebooks, and the distance between two data points can be approximated efficiently from their codes by the precomputed lookup tables. Traditionally, to encode a subvector of a data point in a subspace, only one sub codeword in the corresponding sub codebook is selected, which may impose strict restrictions on the search accuracy. In this paper, we propose a novel approach, named optimized cartesian K-means (ock-means), to better encode the data points for more accurate approximate nearest neighbor search. In ock-means, multiple sub codewords are used to encode the subvector of a data point in a subspace. Each sub codeword stems from different sub codebooks in each subspace, which are optimally generated with regards to the minimization of the distortion errors. The high-dimensional data point is then encoded as the concatenation of the indices of multiple sub codewords from all the subspaces. This can provide more flexibility and lower distortion errors than traditional methods. Experimental results on the standard real-life data sets demonstrate the superiority over state-of-the-art approaches for approximate nearest neighbor search.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Media Technology

How researchers see this paper

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

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Invariant Information Clustering for Unsupervised Image Classification and Segmentation (2018, neutral): “tings. Ex1The core differentiable operator in spatial transformer networks [31]. STL10 CIFAR10 CFR100-20 MNIST Random network 13.5 13.1 5.93 26.1 K-means [51]y 19.2 22.9 13.0 57.2 Spectral clustering [48] 15.9 24.7 13.6 69.6 Triplets [44]z 24.4 20.5 9.94 52.5 AE [5]z 30.3 31.4 16.5 81.2 Sparse AE [3”
A Survey on Learning to Hash (2016, methodology): “an approximation of a data item has already been studied in the signal processing research area, known as multi-stage vector quantization, residual quantization, ormore generally structured vector quantization [38], and recently re-developed for similarity search under the Euclidean distance (additi”
Deep Adaptive Image Clustering (2017, methodology): “(13), we employ the traditional methods (e.g., K-means [32]) to cluster images based on the label features learned by DAC.”
Sparse composite quantization (2015, methodology): “It has been shown that the quantization algorithms [12, 21, 27, 29] achieve better search quality than hashing algorithms with Hamming distance, even with optimized or asymmetric distances [8, 29, 28].”
Learning in high-dimensional multimedia data: the state of the art (2015, methodology): “As discussed in [65, 90], PQ can be taken as optimizing the following problem with respect to C and v i, where v j i is the 1-of-K encoding vector on the j-th subvector and the index of 1 indicates which sub-codeword is used to encode the jth subvector for the i-th vector xi:”
Hashing for Similarity Search: A Survey (2014, unknown): “The idea of using the summation of several dictionary items as an approximation of a data item has already been studied in the signal processing area, known as multi-stage vector quantization, residual quantization, or more generally structured vector quantization [34], and recently re-developed for”