Label-consistent Clustering for Evolving Data

Data analysis often involves an iterative process, where solutions must be continuously refined in response to new data. Typically, as new data becomes available, an existing solution must be updated to incorporate the latest information. In addition to seeking a high-quality solution for the data-analysis task, it is also crucial to ensure consistency by minimizing drastic changes from previous solutions. Applying this approach across many iterations ensures that the solution evolves gradually and smoothly. In this paper, we study the above problem in the context of clustering, specifically focusing on the k-center problem. More precisely, given a set of points X, parameters k and b, and a prior clustering solution ℌ for X, our goal is to compute a new clustering solution C for X, consisting of k centers, which minimizes the clustering cost while introducing at most b changes from ℌ. We refer to this problem as label-consistent k-center, and we propose two constant-factor approximation algorithms for it. We complement our theoretical findings with an extensive experimental evaluation, comparing with state-of-the-art baselines, and demonstrating the effectiveness of our methods on real-world datasets.