Why IndexIVFFlat search empty invlist?

[Kyungmin-Yu]

Summary

I used IndexIVFFlat to search for 11 nearest items, and the result included -1.

Since the dataset size is (60,100) and I used n_list=45 & n_probe=15, I expected to get full result.

Therefore, I invested which cell was searched by this code.

It turns out that index inspected cells that contains 0 items.

I wonder why there is some cells that is empty, and why is IndexIVFFlat selected this cell to search.

Thank you.

Platform

Faiss version: faiss-cpu 1.7.4

Running on:

• CPU

Interface:

• Python

Reproduction instructions

quantizer = faiss.indexFlatL2(100)
index = faiss.IndexIVFFlat(quantizer, 100, 45)
index.train(vectors)
index.add_with_ids(vectors, ids)
index.nprobe = 15

D,I = index.extract_index_ivf(index).quantizer.search(query, 15)
invlists = index.invlists
[invlists.list_size(int(c)) for c in I[0]]

[mdouze]

The cells are selected based on how close they are to the query point.
At selection time, the function does not "know" if the cells are empty.
If you want to make sure to have enough resutls, increase nprobe and set max_codes to a reasonable value.

[Kyungmin-Yu]

Can you explain why empty cells are created during index building, and why empty cells are selected during searching?
I thought IndexIVF selects cell that has nearest centroid vector, but empty cell doesn't have any vector.

[mdouze]

Please refer to https://hal.inria.fr/inria-00514462v2/document