Streaming algorithms for robust max-min diversification

Given a set of n points X in a metric space and an integer k, max-min diversification aims to select k points of X maximizing their minimum pairwise distance. This objective function is however highly vulnerable to noisy points. In[Amagata, AAAI23], a robust formulation is proposed which addresses this vulnerability by excluding solutions containing any of z outliers, defined as the z points in X with the largest nearest-neighbor distances. That paper also presents a coreset-based streaming algorithm for the new formulation, based on a suitable inlier-outlier separation assumption. However, we identify three shortcomings in the algorithm by [Amagata, AAAI23]: its coreset construction requires an offline computation over X, which needs memory linear in n, in stark contrast with the typical goals of stream processing; the one-pass procedure used to extract the solution from the coreset may return fewer than k points (hence, an unfeasible solution) because it permanently discards points too far from the current solution; and its outlier-exclusion guarantee is only probabilistic and weakens as the coreset size shrinks. In contrast, we present a deterministic coreset-based algorithm that, under a natural inlier-outlier separation assumption (similar to the one used in [Amagata, AAAI23]), returns exactly k inliers which are a (2+varepsilon)-approximate solution, for any varepsilon>0, thus only varepsilon above the best polynomial-time sequential approximation, even without outliers. Its one-pass streaming implementation adapts obliviously to the dataset's doubling dimension D and, for wide ranges of k, z, varepsilon, and D, it uses memory independent of n. For sufficiently long streams, its amortized update time is proportional to the coreset size, thus also independent of n.