Source-linked AI summary
Optimized Cartesian $K$-Means
Jianfeng Wang, Jingdong Wang, Jingkuan Song, Xin-Shun Xu, Heng Tao Shen, Shipeng Li
TL;DR
PQ- and CKM-style methods select only one sub codeword per subvector, limiting their ability to reduce distortion. OCKM selects multiple codewords from different sub codebooks, and the paper reports superior ANN performance with reduced quantization error and comparable query time.
Problem
PQ and CKM use only one sub codeword per subvector, limiting distortion reduction and search accuracy.
Source: §1 · p. 2Method
OCKM learns multiple sub codebooks in each subspace and selects one sub codeword from each to encode a subvector.
Source: §4 · p. 4Results
OCKM achieves superior ANN-search performance over state-of-the-art approaches, with reduced quantization error and comparable query time.
Source: §7 · p. 11Takeaways & Limitations
Multiple sub codebooks provide a more flexible encoding that reduces quantization error while keeping query time comparable.
Source: §7 · p. 11Some analysis assumes code selections are uniformly distributed and independent, and one comparison requires M divisible by C.
Source: §4.1.3 · p. 5, §5.1 · p. 6
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
The introduction motivates approximate nearest-neighbor search and reviews quantization methods, then presents OCKM as a way to encode subvectors with multiple codewords from different sub codebooks. It argues this greater flexibility can reduce quantization error and improve search accuracy.
1 INTRODUCTION
- Approximate nearest-neighbor search is more practical than exact search on large, high-dimensional datasets and can achieve orders-of-magnitude speedups with near-optimal accuracy.Source: §1 · p. 1
- Hashing maps data points to compact binary codes, but Hamming distance yields only a few distinct distances and limits distance-approximation flexibility.Source: §1 · p. 1
- PQ decomposes the P-dimensional space into disjoint subspaces with separately learned sub codebooks, while CKM optimally rotates the space to reduce distortion.Source: §1 · p. 2
- OCKM selects multiple sub codewords from different sub codebooks per subvector, whereas PQ and CKM select only one; the paper reports superior ANN performance.The authors characterize PQ and CKM as constrained versions of OCKM under the same code length.Source: §1 · p. 2
2 RELATED WORK
The related-work section contrasts Hamming-embedding methods with quantization approaches for encoding data for nearest-neighbor search. It reviews K-means, PQ, and CKM as foundations for the paper's proposed methods.
2 RELATED WORK
- Hashing methods represent high-dimensional vectors as binary codes; Hamming-embedding approaches use Hamming distance, unlike quantization approaches.Source: §2 · p. 2
2.1 Hamming embedding
- Hamming-embedding methods include linear projections, kernel-based functions, and cosine-generated codes, with approaches differing in how their hash-function parameters are obtained.Examples include LSH and iterative quantization hashing.Source: §2.1 · p. 2
2.2 Quantization
- Quantization methods differ in their constraints on codewords, with K-means, PQ, and CKM presented as representative approaches,,,.Source: §2.2 · p. 2
2.2.1 K-Means
- K-means partitions points into K clusters associated with codewords and learns the codebook by minimizing within-cluster distortion using one-of-K assignments.The codebook and assignments can be optimized iteratively.Source: §2.2.1 · p. 2
2.2.2 Product Quantization
- PQ addresses K-means codebook storage and computation costs by splitting each point into M disjoint subvectors and learning K sub codewords per subspace.With the same cluster count, the passage reports storage falling from O(KMP) to O(KP) and encoding complexity from O(KMP) to O(KP).Source: §2.2.2 · p. 3
2.2.3 Cartesian K-Means
- CKM optimally rotates the original space and learns the rotation matrix by minimizing distortion; constraining the rotation to identity reduces it to PQ.Source: §2.2.3 · p. 3
3 EXTENDED CARTESIAN K-MEANS
ECKM extends PQ and CKM by allowing multiple sub codewords to encode each subvector. Its learning alternates among the rotation, sub codebooks, and code assignments, with the assignment step handled by a practical matching-pursuit-based algorithm.
3 EXTENDED CARTESIAN K-MEANS
- ECKM extends PQ and CKM by allowing C selected sub codewords per subvector, using a nonnegative-integer encoding vector with l1 norm C.The formulation allocates MC log2(K) bits to encode one data point.Source: §3 · p. 3
3.1 Learning
- ECKM learns R, D_m, and b_i by iterative coordinate descent, optimizing one variable while holding the other two fixed.Source: §3.1 · p. 3
3.1.1 Solve R with bm
- With b_m^i and D_m fixed, the rotation update is an Orthogonal Procrustes problem solved using an SVD.Source: §3.1.1 · p. 3
3.1.2 Solve Dm with bm
- With assignments and rotation fixed, each sub codebook D_m is individually updated using (Z_m B_m^T)(B_m B_m^T)^+.Source: §3.1.2 · p. 4
3.1.3 Solve bm
- The code-assignment step is an integer quadratic program, addressed with a practically efficient matching-pursuit-based algorithm.It initializes a residual from the subvector, selects a codeword to reduce distortion, subtracts that codeword, and repeats until C selections are made.Source: §3.1.3 · p. 4
4 OPTIMIZED CARTESIAN K-MEANS
OCKM represents each subvector using C selected codewords from C different subcodebooks, seeking to reduce distortion. Its learning alternates over the rotation, codebooks, and code assignments, while its encoding search trades time for solution quality.
4 OPTIMIZED CARTESIAN K-MEANS
- OCKM uses C different subcodebooks, each contributing a selected subcodeword, to represent each subvector.This expands the single-subcodebook formulation described for ECKM.Source: §4 · p. 4
4.1 Learning
- OCKM learns the rotation, subcodebooks, and code assignments with an iterative coordinate descent algorithm.Source: §4.1 · p. 4
4.1.1 Solve R with Dm,c and bm,c
- With the codebooks and assignments fixed, optimizing R becomes an Orthogonal Procrustes Problem.Source: §4.1.1 · p. 4
4.1.2 Solve Dm,c with R and bm,c
- With R and the assignments fixed, each subcodebook can be solved by matrix (pseudo)inversion.Source: §4.1.2 · p. 5
4.1.3 Solve bm,c
- Multiple best candidates matching pursuit searches the top T candidates in each step and recursively encodes the remaining subcodebooks.The selected final code is the candidate with the smallest distortion error; larger T improves the solution but increases encoding time, and the paper chooses T = 10 as a tradeoff.Source: §4.1.3 · pp. 5–6
5 DISCUSSIONS
OCKM’s discussion compares its distortion guarantees with CKM and examines constraint choices, optimization, and query cost. For exhaustive search, its query time is comparable to CKM in the reported SIFT1M example.
5.1 Connections
- With the same code length, OCKM’s distortion is no larger than CKM’s, and it can potentially be lower with fixed M and K.The comparison follows from constructing a feasible OCKM solution with the same objective value as CKM’s optimum.Source: §5.1 · p. 6
5.2 Inequality Constraints or Equality Constraints
- Under the inequality constraint, the objective value remains the same as for the corresponding equality solution, while equality may yield lower distortion at the same M and K.At the same code length, the inequality constraint cannot outperform equality.Source: §5.2 · p. 7
5.3 Implementation
- To keep the iterative coordinate-descent objective non-increasing, OCKM updates codes only when codes from Algorithm 1 or Algorithm 2 can provide a lower distortion error.On the SIFT1M training set, each iteration took about 4.2 seconds; all experiments used 100 iterations.Source: §5.3 · p. 7
5.4 Distance Approximation for ANN search
- 24.3ms for OCKM versus 23.5ms for CKM on SIFT1M, with both using 64-bit codes; OCKM requires one additional lookup and addition.The paper says the practical query-time differences are minor and accuracy can potentially be better with OCKM.Source: Table 2 · p. 8, §5.4 · p. 8
6 EXPERIMENTS
Experiments on SIFT1M, GIST1M, and SIFT1B compare OCKM with PQ, CKM, and ECKM using distortion, recall, and mean overall ratio. OCKM achieves the strongest reported results across the fixed-subvector and fixed-code-length comparisons.
6.1.1 Datasets
- The evaluation uses SIFT1M, GIST1M, and SIFT1B, each with training, query, and database sets; the approaches compared are OCKM, PQ, CKM, and ECKM.K is set to 256; approach labels distinguish asymmetric and symmetric approximate distances with the suffixes -A and -S.Source: §6.1.1 · p. 8, §6.1.3 · p. 9
6.1.2 Criteria
- The evaluation reports distortion, recall, and mean overall ratio; lower values are better for distortion and mean overall ratio, while recall measures whether the true nearest neighbor appears among top-ranked vectors.Mean overall ratio summarizes the quality of ranked neighbors, with 1 corresponding to the exact-search results.Source: §6.1.2 · p. 8
6.2.1 Comparison with the number of subvectors fixed
- At the same number of subvectors, OCKM has the lowest distortion, highest recall, and lowest mean overall ratio among approaches using the same approximate-distance type.The distortion comparison covers training and database sets; recall and mean overall ratio are reported at the 10-th ranked point.Source: §6.2.1 · p. 9, Figure 3 · p. 9, Figure 4 · p. 9
6.2.2 Comparison with the code length fixed
- At equal code lengths, OCKM generally outperforms the other approaches under the same approximate-distance type, with about 5, 4, and 4 percent recall improvement on SIFT1M, GIST1M, and SIFT1B, respectively.For asymmetric distance at 64 bits, these improvements are reported at the 10-th ranked point; OCKM also has the lowest database-set distortion at equal code length on SIFT1M and GIST1M.Source: §6.2.2 · p. 9, Figure 7 · p. 10, Figure 8 · p. 10
- OCKM's recall advantage is larger at smaller code lengths, while OCKM and CKM recalls approach 1 at larger code lengths.The comparison extracts recall at the 100-th nearest neighbor.Source: §6.2.2 · pp. 9–10, Figure 9 · p. 11
- ECKM is not very competitive at equal code length; the authors suggest its smaller number of sub codebooks as a possible reason.At 64 bits, ECKM has four sub codebooks, versus eight for PQ, CKM, and OCKM; it nevertheless beats PQ on GIST1M, which the authors say is more sensitive to rotation.Source: §6.2.2 · p. 10
7 CONCLUSION
OCKM encodes high-dimensional data points for approximate nearest neighbor search using multiple sub codebooks in each subspace. The paper concludes that this reduces quantization error with comparable query time at the same code length, and reports superior ANN performance over state-of-the-art approaches.
7 CONCLUSION
- OCKM uses multiple sub codebooks in each subspace, each contributing a sub codeword to encode the subvector.The paper reports reduced quantization error with comparable query time at the same code length, and superior ANN performance over state-of-the-art approaches.Source: §7 · p. 11