facebookresearch / faiss

A library for efficient similarity search and clustering of dense vectors.

https://faiss.ai

MIT License

31.12k stars 3.62k forks source link

Support O(1) removal on IDMap2,Flat #1164

Open bfelbo opened 4 years ago

bfelbo commented 4 years ago

Platform

Running on:

[x] CPU
[ ] GPU

Interface:

[ ] C++
[x] Python

Feature Request

It would be incredible if you could support the O(1) removal on IndexIDMap2 similar to how it's now added on IndexIVF. IndexFlatL2 is working amazingly for our use case except for the O(N) removal. It would be great to not have to add the complexity of training an IndexIVF to get the O(1) removal.

bfelbo commented 4 years ago

Response from @mdouze on Facebook thread:

it is true that O(1) removal could be implemented for IDMap2,Flat by just moving in the last element. Pleas fill an issue for this, we’ll put it on the todo list.

bfelbo commented 4 years ago

@mdouze I can also try to take a look at this if you can guide me where to start?

mdouze commented 4 years ago

Thanks! The steps are:

use a IDSelectorArray https://github.com/facebookresearch/faiss/blob/master/impl/AuxIndexStructures.h#L77 to store the list of elements to remove
in IDMap2::remove, https://github.com/facebookresearch/faiss/blob/master/MetaIndexes.cpp#L187 make a special case if sel is a IDSelectorArray and if the sub-index is a Flat index --> then just make a loop over elements to remove that moves that last element to the element to remove and updates the map and the rev_map

mdouze commented 2 years ago

relocated to

https://github.com/facebookresearch/faiss/blob/main/faiss/MetaIndexes.cpp#L187