Fully dynamic k-center clustering in low dimensional metrics

Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric k-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the k-center clustering problem that provably achieves a (2 + ∊)-approximation in nearly logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and ∊ is a constant. An important feature of our algorithm is that the update and query times are independent of k. We confirm the practical relevance of this feature via an extensive experimental study which shows that for large values of k, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time.