Clustering with Set Outliers and Applications in Relational Clustering

We introduce and study the k -center clustering problem with set outliers, a natural and practical generalization of the classical k -center clustering with outliers. Instead of removing individual data points, our model allows discarding up to z subsets from a given family of candidate outlier sets H. More formally, given a metric space (P,dist), where P is a set of elements and dist a distance metric, a family of sets H ⊆ 2 P , and parameters k, z, the goal is to compute a set of k centers C ⊆ P and a family of z sets H ⊆ H such that C∩(⋃ h ∈ H h)=∅ to minimize max p ∈ P∖(⋃ h ∈ H h) min c ∈ C dist (p,c) (clustering cost). This abstraction captures structured noise common in database applications, such as faulty data sources or corrupted records in data integration and sensor systems. We present the first approximation algorithms for this problem in both general and geometric settings. Our methods provide tri-criteria approximations: selecting up to 2k centers and 2f z outlier sets (where f is the maximum number of sets that a point belongs to), while achieving constant-factor approximation in clustering cost. In geometric settings, we leverage range and BBD trees to achieve near-linear time algorithms. In many real applications f=1. In this case we further improve the running time of our algorithms by constructing small coresets. We also provide a hardness result for the general problem showing that it is unlikely to get any sublinear approximation on the clustering cost selecting less than f • z outlier sets. We demonstrate that this model naturally captures relational clustering with outliers. We define and study two new formulations: one where outliers are result tuples in a join, and another where outliers are input tuples whose removal affects the join output. We provide approximation algorithms for both, establishing a tight connection between robust clustering and relational query evaluation.