Week 11 (6) Passage Retrieval – Scaling Up

1. Passage Retrieval and Similarity Search

How to find the passage in real time? -> Similarity Search

1) MIPS (Maximum Inner Product Search)

주어진 질문(query) 벡터 q에 대해 Passage 벡터 v들 중 가장 질문과 관련된 벡터를 찾아야함

(관련성은 inner product 값으로 계산)

• 검색 : 인덱싱 된 벡터들 중 질문 벡터와 가장 내적값이 큰 상위 k개의 벡터를 찾는 과정
• 인덱싱 : 방대한 양의 passage 벡터들을 저장하는 방법
• brute-force(exhaustive) search : 저장해둔 모든 Sparse/Dense 임베딩에 대해 일일히 내적값을 계산하여 가장 값이 큰 passage 추출
  • 실제로 검색해야 할 데이터는 훨씬 방대하기 때문에 더이상 모든 문서 임베딩을 일일히 보면서 검색할 수 없음

2) Tradeoffs of similarity search

2. Approximating Similarity Search

1) Compression - Scalar Quantization(SQ)

compression : vector를 압축하여, 하나의 vector가 적은 용량을 차지 -> 압축량 ↑ => 정보 손실 ↑

ex) scalar quantization

2) Pruning - Inverted File (IVF)

pruning : Search space를 줄여 search 속도 개선(dataset의 subset만 방문)

쿼리에 가장 근접한 cluster만 보는 방식. 그 내의 포인트에 대해서는 exhaustive search로 모두 검색.ex) k-means clustering

 

+ FAISS : Library for efficient similarity search (indexing 쪽을 도움. endoing은 x)