Product quantization for nearest neighbor search

Product quantization for nearest neighbor search

 Jegou, Herve, Matthijs Douze,
 Pattern Analysis and Machine Intelligence 2011

nearest neighbor search (NN earch):







在高維度的情況下，NN search很花時間，
所以我們可以使用A(aproximate)NN search，
而評估ANN search的好壞則根據效率與搜尋品質的妥協來決定，
但是實際上我們應該要考慮到空間的使用，
很多像是E2LSH這樣的演算法是很花空間的



這篇paper試著利用將高維的像量轉移到低維的像量的積，
並且引入inverted file system來達到提高效率與搜尋品質的任務，
並且同時考量的空間的使用。

 一、Background :Quantization , Product Quantization

 
   1. vector quantization :
    一個函數q將D維的向量映射到一個有限大小的向量(centroid)群(codebook)中的其中一個
     
       Voronoi cell : 所有分配到該centroid的向量!

    判斷quantizer的好壞 : mean squared error



   


quantizer :

     
     




但是當K(code book size)的大小很大的時候，使用k means 是很困難的事情
事實上，光光是要存下k 個 centroids都已經是不可能的事情了
針對這個問題，product quantizers就被提出了
     


  2. product quantizers :



 

   
   
   



   

 二、searching with quantization

  1.computing distance using quantized codes
   
  Symmetric distance computation (SDC):

     
 ASymmetric distance computation (ADC):

 2.analysis of distance error







3.estimator of the squared distance

三、non exhaustice search

1.coarse quantizer locally defined product quantizer

2.indexing structure



3.search algorithm

四、evaluation of NN search