In a naive delete, we walk up the layers of the graph and delete every K + neighboring references to K. Over time, this may lead to a decay of the clustering coefficient as the average number of neighbors falls under M, thus threatening search performance and accuracy. This is especially true if Deletes are away from new Adds.
To fix, we need to iterate all old neighbors of a Delete and replenish their neighbors up to M. Unfortunately the cost of this operation is $M^2 \cdot log(n)$ where n is the number of nodes in the entire graph. Even more unfortunate, all of this is difficult to explain to the typical user looking for a quick-fix ANN solution.
In a naive delete, we walk up the layers of the graph and delete every K + neighboring references to K. Over time, this may lead to a decay of the clustering coefficient as the average number of neighbors falls under M, thus threatening search performance and accuracy. This is especially true if Deletes are away from new Adds.
To fix, we need to iterate all old neighbors of a Delete and replenish their neighbors up to M. Unfortunately the cost of this operation is$M^2 \cdot log(n)$ where n is the number of nodes in the entire graph. Even more unfortunate, all of this is difficult to explain to the typical user looking for a quick-fix ANN solution.