search

facebookresearch / faiss

A library for efficient similarity search and clustering of dense vectors.
https://faiss.ai
MIT License
31.34k stars 3.64k forks source link

How to use OPQ to reduce the dimensions #251

Closed zhaokang0826 closed 6 years ago

zhaokang0826 commented 6 years ago

I have read the paper：Polysemous Codes in ECCV2016

I have an question：In the paper, you say “Alexandre Sablayrolles had the idea of extending the OPQ method to reduce the number of dimensions”. The original OPQ can not reduce the dimensions.

I want to know how to use OPQ to reduce the dimensions?

Thank you!

alexandresablayrolles commented 6 years ago

If you look at the formulation in the original paper "Optimized Product Quantization for Approximate Nearest Neighbor Search" (CVPR'13), it turns out you can use Algorithm 1 with a non-square R matrix (say d*p). You just need to initialize it so that R^T R = I and you follow the steps described, as all the subsequent matrices will have the right number of dimensions.