Optimized Product Quantization and Locally Optimized Product Quantization

[futurely]

In 2013, there are two important improvements of Product Quantization. Optimized Product Quantization non-parametric solution [2] was equivalent to the Cartesian k-means [1] and performed better than PQ. In 2014, Locally Optimized Product Quantization [3] further improved upon OPQ.

SIFT1B with 64-bit codes, K=213=8192 and w=64. For Multi-D-ADC, K=214 and T=100K.

SIFT1B with 128-bit codes and K=213=8192 (resp. K=214) for single index (resp. multi-index). For IVFADC+R and LOPQ+R, m′=8, w=64.

1. Mohammad Norouzi, David J. Fleet. Cartesian k-means. IEEE Computer Vision and Pattern Recognition (CVPR), 2013.
2. Optimized Product Quantization, by Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun, in TPAMI.
3. Y. Kalantidis, Y. Avrithis. Locally Optimized Product Quantization for Approximate Nearest Neighbor Search. In Proceedings of International Conference on Computer Vision and Pattern Recognition (CVPR 2014), Columbus, Ohio, June 2014.

[futurely]

LOPQ is quite straightforward to implement. For training, ProductQuantizationLearning trains an independent product quantizer for each coarse centroid instead of only one for all centroids. For testing, IVFPQ applies the corresponding PQ for the centroid to which the query vector is nearest. As LOPQ illustrated, soft assignment to the coarse centroids could lead to higher recall.

Multiple PQ model files would be easier to manage with #6.

[lefman]

Indeed there are several papers that improve over standard Product Quantization that is implemented here. In case you are interested, we would welcome a contribution of such a method to the project!