Faiss.indexIVFFlat 설명 및 코드,실험 결과

IndexIVFFlat

quantizer가 quantization index (cluster)를 생성한 후,

각 query vector와 가까운 vector를 전부 search하는 게 아니라

가까운 몇몇 quantization index (cluster) 내의 vectors들에 대해서만 search하여 Knn을 찾는 방법.

TopK에 속하는 vector임에도 search하는 cluster에 없을 경우 데이터가 누락될 여지가 있음.

cluster를 생성해야 하기 때문에 train 과정이 필요함

nprobe (index.nprobe)

best cluster외에도 근방의 cluster 몇 개를 search할지를 설정, nprobe가 높을수록 exact 방법의 결과와 비슷해짐

voronoi cell diagram (빨간 점이 quantization index 라고 생각하면 됨)

참고자료: https://faiss.ai/cpp_api/struct/structfaiss_1_1IndexIVF.html, https://checkwhoiam.tistory.com/84

Faiss L2 distance (Euclidean distance)

---

일반(exact) search 방식

vector_sample = np.load('vectors.npz')
size, dim = vector_sample.shape
index = faiss.IndexFlatL2(dim)
index.add(vector_sample)
distances, indices = index.search(vector_sample, k=80)

IVF quantizer 방식

metric = faiss.METRIC_L2
size, dim = vector_sample.shape
nlist = min(4096, 8 * round(math.sqrt(size)))
index = faiss.IndexFlatL2(dim)
quantizer = index
index = faiss.IndexIVFFlat(quantizer, dim, nlist, metric)
index.train(vector_sample)
index.add(vector_sample)
index.nprobe = 128
ivf_distances, ivf_indices = index.search(vector_sample, k=80)

Faiss Cosine similarity

---

일반(exact) search 방식

vector_sample = np.load('vectors.npz')
size, dim = vector_sample.shape
index = faiss.IndexFlatIP(dim)
index.add(vector_sample)
cos_similarity, cos_indices = index.search(vector_sample, k=80)

IVF quantizer 방식

metric = faiss.METRIC_INNER_PRODUCT
size, dim = vector_sample.shape
nlist = min(4096, 8 * round(math.sqrt(size)))
index = faiss.IndexFlatIP(dim)
quantizer = index
index = faiss.IndexIVFFlat(quantizer, dim, nlist, metric)
index.train(vector_sample)
index.add(vector_sample)
index.nprobe = 128
cos_ivf_similarities, cos_ivf_indices = index.search(vector_sample, k=80)

10만개짜리 embedding 값에 대한 실험 결과

vector_sample.shape = (120000 , 256)

top 80 결과

방식	nprobe	exact 결과와 매치	search 시간
FlatIP (exact)	-	80/80	135s
FlatIP + IVF	5	71/80	0.56s
FlatIP + IVF	10	77/80	0.96s
FlatIP + IVF	40	79.3/80	3.17s
FlatIP + IVF	128	79.7/80	8s

nprobe를 128까지 올리면 search시간은 10배이상 빠르고 정확도도 거의 비슷한 것을 볼 수 있다!

Uploaded by N2T