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:

Iterate over every node in the graph
If level 0 of this node's outgoing edges does not include the to-be-deleted item, skip node
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?

Support deleting elements? #4

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions