Product quantization for nearest neighbor search (Herve ́ Je ́gou, Matthijs Douze, Cordelia Schmid)
這也是一篇 journal paper (IEEE PAMI 2011)，內容一樣寫的很詳細，主要是提出 product quantization 來將要 quantize 的 vector 切成 m 段 subvector 後，再對 subvector 去做 quantize ，最後再將結果 concate 起來當成原本的 quantization result，如此可以大幅加快找出 centroids 的速度，並大幅降低使用的 memory。
會提出這個作法主要是因為：
- 在 high dimension 的 nearest neighbor search 會有 the curse of dimension
- 而目前 state-of-art 的方法（E2LSH ＆ FLANN）在reranking階段時，需要將原本的 vector 也放到 memory 中，所以限制了 database vector 的最大數量
另外，在算 query vector 與 database vector 距離的時候，paper 提出了兩種計算上速度差不多的算法（SDC & ADC）。兩者計算時的相同點是，database 的 vector 都先 quantize 過。而相異點是，query vector 一個是先 quantize 完再去算 Euclidean distance（symmetric distance computation SDC），另一個是 query vector 不 quantize，直接算 Euclidean distance（asymmetric distance computation ADC），而實驗結果告訴我們 ADC 的結果比 SDC 的結果來的好。
優點是，這兩中方法 don't depend on database size n ，所以可以有很好的 scalability
最後，paper 也提出了 ADC 結合 inverted file system 的方法（IVFADC）避免 exhaustive search 進而加速 retrieval 的速度。而更貼心的是，這邊 journal paper 也做了許多實驗告訴我們各種方法的優劣跟怎樣的參數是最好的（k^* = 256 & m = 8 for 128 dimension SIFT），不用擔心 reproduce 不出 paper 的結果。
