PQ (product quantization) 기반 ANN

PQ에 대해서 잘 정리된 문서 

• Faiss & Product Quantization (한글 문서) 
• 딥러닝 Quantization [시리즈 2/3] – Product quantizaton 알아보기 (한글 문서) 
• Product Quantizers for k-NN Tutorial Part 1 (영어 문서) 

PQ 기반 ANN 

• 참고 문서: Product Quantizers for k-NN Tutorial Part 1 (영어 문서) 
• ANN으로 질의와 관련된 문서를 검색하는 것으로 가정함. 그래서 질의 벡터와 유사한 문서 벡터를 찾는 작업임. 
• 문서 벡터는 PQ를 이용해서 표현. 즉, 문서 벡터를 구성하는 각 서브 벡터(subvector)와 가장 가까운 centroid로 표현. 벡터당 n개의 서브 벡터가 있다면, 문서는 n개의 centroid로 표현됨. 
• 질의 벡터의 각 서브벡터와 해당 서브 스페이스(sub space)의 centroid들과의 유사도를 미리 계산함. 즉. (질의 벡터의 서브 벡터, centroid) 의 유사도 값이 계산됨. 
• 질의 벡터와 문서 벡터의 유사도 계산: 질의 벡터의 서브 벡터와 문서 벡터의 서브 벡터의 centroid간의 유사도 합으로 계산함. 이 계산은 앞단에서 구한 (질의 벡터의 서브 벡터, centroid) 유사도 값을 가져오면 됨. 
• 문제점: 
• 질의 벡터와 모든 문서 벡터간의 유사도를 계산해야 하는지? 문서 벡터가 수천만개라고 했을 때는? 
• 질의 벡터의 서브 벡터와 가까운 centroid를 찾고, 이 centroid를 가진 문서들만을 대상으로 하는 방법도 있을 듯.