# Optimized Cartesian K-Means

arXiv: https://arxiv.org/abs/1405.4054 · HTML: https://mlsanity.com/paper/1405.4054/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2014.

## Built on by (most cited first, 14 of 14)

- [IRGen: Generative Modeling for Image Retrieval](https://mlsanity.com/paper/2303.10126/) (2023)
- [Discrete Tokenization for Multimodal LLMs: A Comprehensive Survey](https://mlsanity.com/paper/2507.22920/) (2025)
- [On PyTorch Implementation of Density Estimators for von Mises-Fisher and Its Mixture](https://mlsanity.com/paper/2102.05340/) (2021)
- [Deep adaptive fuzzy clustering for evolutionary unsupervised representation learning](https://mlsanity.com/paper/2103.17086/) (2021)
- [Deep Variational Clustering Framework for Self-labeling of Large-scale Medical Images](https://mlsanity.com/paper/2109.10777/) (2021)
- [AugNet: End-to-End Unsupervised Visual Representation Learning with Image Augmentation](https://mlsanity.com/paper/2106.06250/) (2021)
- [Neural Mixture Models with Expectation-Maximization for End-to-end Deep Clustering](https://mlsanity.com/paper/2107.02453/) (2021)
- [Joint Debiased Representation Learning and Imbalanced Data Clustering](https://mlsanity.com/paper/2109.05232/) (2021)
- [Deep Online Probability Aggregation Clustering](https://mlsanity.com/paper/2407.05246/) (2024)
- [Learning the Precise Feature for Cluster Assignment](https://mlsanity.com/paper/2106.06159/) (2021)
- [Contrastive Representation Disentanglement for Clustering](https://mlsanity.com/paper/2306.05439/) (2023)
- [Graph Probability Aggregation Clustering](https://mlsanity.com/paper/2502.19897/) (2025)
- [TemporalFlowViz: Parameter-Aware Visual Analytics for Interpreting Scramjet Combustion Evolution](https://mlsanity.com/paper/2509.04834/) (2025)
- [Block-Sphere Vector Quantization](https://mlsanity.com/paper/2605.19972/) (2026)

## Abstract (arXiv)

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 (OCKM), to better encode the data points for more accurate approximate nearest neighbor search. In OCKM, 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 datasets demonstrate the superiority over state-of-the-art approaches for approximate nearest neighbor search.