Dynamic Local Search Under Distance Updates for $(k,z)$-Clustering

Machine learning systems often cluster data that keep changing, such as embeddings that drift during training or networks that keep gaining connections. We introduce a model of dynamic metric spaces in which the point set is fixed and distances only decrease, as happens for example when edges are inserted into a graph and shortest paths shrink. In this model we study a local search approach for $(k,z)$-clustering, a generalization of $k$-median and $k$-means objectives. The main computational cost of local search is finding an improving swap, a pair of one center and one non-center whose exchange lowers the value of the objective function. We give a deterministic dynamic algorithm that maintains the best improving swap in time $O(n\log n)$ per distance update, instead of $O(n^2)$ from scratch. Building on this data structure, we design an algorithm that maintains a constant factor approximate $(k,z)$-clustering with total update time $\tilde{O}(k{n}^2)$, matching (up to lower order terms) one single run of the fastest deterministic static local-search based approximation algorithm. On the metric space induced by two real evolving graphs with up to 55,000 vertices, our algorithm matches the quality of full recomputation to within 0.25 percent, while running far faster: it handles 1,000 edge insertions in about 10 s, compared to the roughly 5,100 s of a warm start approach which uses the previously computed solution, and to over a week through a naive full recomputation from scratch.