Support deleting elements?

[ThomasDelteil]

Thanks for the great implementation, the performance is impressive. I was wondering what it would take to add the ability to delete an element from the graph without degrading too much the performance? Having a special flag on the label, or re-assigning the lost edges?

[searchivarius]

This works mostly fine for SW-graph:
https://github.com/nmslib/nmslib/blob/master/test_batch_app/test_batch_mod.cc

Doing something similar for HNSW is a bit more work, but not too much. My understanding is that HNSW will actually be much more robust to deletion. One disadvantage is that you can't use an optimized static index any more (but that's the cost of all dynamic data structures): At least, something

[yurymalkov]

Hi @ThomasDelteil,
the optimal solution strongly depends on the scenario and the amount of performance you are willing to lose).

1. Deletion by flagging the elements is easy to implement and is OK if the number of deletions is small and/or they are random. However, just using flagging will not stop the degradation of performance.
   Imagine you have a 1B dataset consisting of two well-isolated clusters (i.e. two very different classes). You mark every element from the first cluster as deleted and then query the nearest neighbor of an element from the "deleted" cluster.
   The search will turn to (almost) exhaustive as you would have to go through all of 0.5B the deleted elements to find just a single nearest neighbor from the second (non-deleted) cluster (as all elements from the deleted cluster are closer to the query than any second-cluster element).
2. As you have mentioned, you can do full reassignments of the edges. This allows keeping the index fresh, no matter how many deletions there were. However, reassignments lead to extra work during the deletion and are somewhat trickier to implement compared to sw-graph (although I see no problem with the optimized hnswlib index).

Agree with @searchivarius. HNSW should be much more robust, as it does not depend on the data order. SW-graph (NSW) can be easily crippled on low-dim data if the first inserted elements are removed.

[phdowling]

Any chance this will be added, either here or in nmslib, some time soon?

[searchivarius]

@phdowling sometime, it will. SW-graph in NMSLIB has an experimental deletion feature, but it's not exposed to Python.

[yurymalkov]

@phdowling I do not think I will have an opportunity to add deletions to hnswlib for several following months.
But if someone willing to contribute I can help.

[linzuk]

Does any hero implement deletion feature. We are looking forward to it.

[popupz]

@yurymalkov could you describe what the process of reassignments of the edges ?

would a naive approach of simply removing the node from the connected nodes on all layers work. those should be easy to find since the links are bi-directional

edit : on second thought links are not bi-directional because only the strongest links on each level are preserved. So would the only option then be to make a pass through all nodes in the graph and rewrite those nodes that have connections to the item being deleted

[gasabr]

Have not seen all the code yet, but is there a workaround for solving this issue, like saving and loading index or recreating is the only way to do "hard delete"?

[etiennedi]

@popupz

edit : on second thought links are not bi-directional because only the strongest links on each level are preserved. So would the only option then be to make a pass through all nodes in the graph and rewrite those nodes that have connections to the item being deleted

I ran into a similar issue building the deletion feature for the HNSW implementation in Weaviate (which is written in Golang). Weaviate is a general-purpose database/search engine, so we can't predict in what order or frequency users will be deleting items, so the "flagging-only" approach also isn't feasible for us, for the reasons @yurymalkov outlined very well above. I'd like to share my findings and also present an idea of I'm planning to tackle this issue. Feedback much appreciated.

Naive approach

I first tried following all edges of the to-be-deleted items and simply reassigning those, i.e. what you described as the "naive approach". However, even at a very small dataset (1000 nodes, maxNeighbors=30, efConstruction=128) I noticed that less than half of the edges pointing to the deleted item would be removed. I.e. the other half have become uni-directional edges. As you outlined, this is to be expected as only the strongest links are preserved. However, I wouldn't have expected that the effect is this noticeable on such a small HNSW graph already. Either way, this clearly shows, that the naive approach isn't very helpful.

Brute force approach

So next I tried the brute-force approach of:

1. Iterate over every node in the graph
2. If level 0 of this node's outgoing edges does not include the to-be-deleted item, skip node
3. On the remaining nodes, remove all edges and re-assign them using the same procedure on insert (making sure we exclude the to-be-deleted item)

This works well, all the edges are cleaned up and the quality of the index isn't harmed. However, this is terribly slow. Even on my tiny graph deleting all the items took about 10 times as long as inserting them. I don't see this feasible on a graph with a few million or billion nodes.

Idea: Tombstones with periodic clean up

My idea to solve this issue is to combine the "flagging approach" with a periodical reassignment of edges. It would look roughly like this:

On Delete:

• Attach a tombstone to the to-be-deleted item
• Append node id to a list of nodes with tombstones (basically a temporary index to quickly find all deleted nodes)

On Search:

• Skip each element that has a tombstone attached

Periodically (with configurable frequency):

• If list of tombstones is empty, don't do anything, else:
• Iterate over ever node in the graph
• If node has no outgoing edges to a tombstoned node skip, else:
• Delete all edges and reassign
• Once the reassignment of a node is done, remove the node's id from the list of tombstoned nodes

Possible Benefits

• There is immediate feedback to a user sending a delete request, as adding a tombstone is very cheap
• The deleted item will immediately be excluded from future searches
• The search performances degrades slightly (as outlined by @yurymalkov) with each additional tombstone, however the periodic clean up will make sure the amount of tombstones stays low
• The clean up procedure is very robust: If the cleanup fails after cleaning up only 1/3 of the graph (e.g. through a random server crash), those nodes will simply be skipped in the next clean up cycle, and clean up will continue on the next node that requires clean up.
• Regardless of how many deletes, at the very most we'll reassign every node once per clean up cycle. If we were to do re-assigns on every delete there is no upper limit to how many reassigns are required. In other words: A node that has outgoing edges to n tombstoned nodes per cycle will be reassigned once instead of n times.
• During a clean up, the search quality should not change: Since a tombstoned node is skipped in a search anyway, the result quality will not change regardless of whether a clean up job is currently running or not.

Any thoughts on my outlined approach? Is there any way we can avoid a brute-force cleanup which needs to read every single node in the graph?

[yurymalkov]

Hi @etiennedi for a detail analysis. I agree that might be a very good solution!
One thing is that it needs global operation once in a while, but this should not be an actual problem.

Another option is when a new element is being added to pick one of the deleted (tombstoned) elements and update it to the position of the new element. The downside is that it cannot shrink the index at any time (e.g. it makes sense to remove unused element during index saving).
Note that tombstoning the elements and element updates is implemented in hnswlib.