FAISS 인덱스 종류 — Flat·IVF·HNSW·PQ 이해하기

FAISS 인덱스 종류 — Flat·IVF·HNSW·PQ 이해하기

FAISS가 제공하는 인덱스는 크게 정확 검색(Flat) 과 근사 검색(IVF, HNSW, PQ) 으로 나뉘어요. 정확도와 메모리·속도를 어떻게 바꿀지에 따라 고릅니다. 인덱스는 클래스 생성자로 만들 수도 있고 index_factory 문자열로 만들 수도 있어요.

출처: https://github.com/facebookresearch/faiss/wiki/Faiss-indexes

주요 기본 인덱스 요약

Method Class name index_factory Main parameters Exhaustive Comments
Exact Search for L2 IndexFlatL2 "Flat" d yes brute-force
Exact Search for Inner Product IndexFlatIP "Flat" d yes also for cosine (normalize vectors beforehand)
HNSW graph exploration IndexHNSWFlat "HNSW,Flat" d, M no
Inverted file with exact post-verification IndexIVFFlat "IVFx,Flat" quantizer, d, nlists, metric no
Scalar quantizer (SQ) in flat mode IndexScalarQuantizer "SQ8" d yes
Product quantizer (PQ) in flat mode IndexPQ "PQx" d, M, nbits yes
IVFADC (coarse quantizer+PQ on residuals) IndexIVFPQ "IVFx,PQy" quantizer, d, nlists, M, nbits no

Flat 인덱스

Flat 인덱스는 벡터를 고정 크기 코드로 인코딩해 ntotal * code_size 바이트 배열에 저장해요. 검색 시 모든 인덱스된 벡터를 순차적으로 복호화해 질의와 비교합니다. 정확하지만 벡터 수가 많아지면 느려져요. 여기에 ID는 저장하지 않아 add_with_id를 지원하지 않지만, IndexIDMap으로 감싸면 기능을 추가할 수 있습니다.

압축 정도에 따른 인코딩 종류는 요약하면 이렇습니다.

  • 압축 없음 (IndexFlat)
  • 16비트 부동소수점 (IndexScalarQuantizer)
  • 8/6/4비트 정수 양자화 (IndexScalarQuantizer)
  • PQ 인코딩 (IndexPQ)
  • 잔차 인코딩 (IndexResidual)

Cell-probe 방법 — IndexIVF

가장 가까운 이웃을 항상 찾는다는 보장을 조금 내려놓는 대신 속도를 올리는 전형적인 방법이 k-means 기반 분할이에요. IVF에서는 특징 공간을 nlist 개의 셀로 나누고, 각 데이터베이스 벡터를 가장 가까운 클러스터에 할당해 역파일(inverted file) 구조에 저장합니다.

검색 시에는 nprobe 개의 역파일 목록만 골라 질의와 비교해요. 그래서 데이터베이스의 일부만 검색하므로 훨씬 빠르죠. nprobe는 검색 시점에 지정해서 속도와 정확도의 트레이드오프를 측정하기 좋습니다. 실패 케이스는 최근접 이웃의 셀이 선택되지 않을 때 발생해요. 대략적인 경험칙으로 클러스터 수 nlist는 C * sqrt(n) 정도를 잡습니다.

경험상 IndexIVFPQ 가 대규모 검색에 가장 유용한 구조 중 하나예요.

coarse_quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFPQ(coarse_quantizer, d, ncentroids, code_size, 8)
index.nprobe = 5

code_size는 보통 4~64 사이의 2의 거듭제곱을 쓰고, PQ와 마찬가지로 d는 서브양자화기 수의 배수여야 합니다.

HNSW

HNSW(Hierarchical Navigable Small World)는 인덱스된 벡터 위에 그래프를 만들어 검색 시 빠르게 최근접 이웃으로 수렴하게 해요. 주요 파라미터는 M(그래프 이웃 수, 클수록 정확하지만 메모리 증가), efConstruction(추가 시 탐색 깊이), efSearch(검색 탐색 깊이)예요. HNSW는 벡터 삭제를 지원하지 않는데, 삭제가 그래프 구조를 깨뜨리기 때문입니다.

PQ(Product Quantization)

PQ는 벡터를 여러 서브벡터로 나눠 각각 소량의 비트(보통 8비트)로 양자화해 메모리를 크게 줄이는 방식이에요. n_bits는 8, 12, 16 중 하나여야 하고, 차원 d는 서브양자화기 수 m의 배수여야 해요.

m = 16                   # number of subquantizers
n_bits = 8               # bits allocated per subquantizer
pq = faiss.IndexPQ(d, m, n_bits)  # Create the index
pq.train(x_train)        # Training
pq.add(x_base)           # Populate the index
D, I = pq.search(x_query, k)  # Perform a search

더 알아보기