Support O(1) removal on IDMap2,Flat

[bfelbo]

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]

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]

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

[mdouze]

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]

relocated to

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