Streaming algorithms for robust max-min diversification

Andrea Pietracaprina; Geppino Pucci; Stefano Zanon

cs.LGOct 1, 2026

Streaming algorithms for robust max-min diversification

Authors: Andrea Pietracaprina, Geppino Pucci, Stefano Zanon

Organizations: Department of Information Engineering, University of Padova, Italy

Abstract

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$ .

Figures & tables

Panel of Figure 1 — Figure 1: Visual execution of the second phase of the Coreset algorithm presented in [ 4 ] .

Explore similar work

May 15, 2026stat.ML

MaxSketch: Robust Distinct Counting in Streams via Random Projections

Estimating the number of distinct elements in a data stream is well understood when repeated elements are identical. In modern settings, however, observations are high-dimensional and noisy, so repeated instances of the same object are only approximately similar -- for example, different images of the same individual may vary significantly at the pixel level. Classical sketches such as HyperLogLog rely on consistent hash values for identical elements and break down in this regime. Recent work on robust distinct counting in general metric spaces achieves

\widetildeΘ(\sqrt{n})

memory, which is tight in the worst case. We show that substantially improved memory guarantees are possible under geometric structure common in learned representations. We introduce MaxSketch, a simple max-linear sketch built from random Gaussian projections, and prove that it succeeds in estimating the number of distinct latent objects. Concretely, we show that under this assumption

m = \widetilde{O} (\log n / \varepsilon^2)

random projections (and hence

\widetilde{O} (\log n/\varepsilon^2)

memory) suffice to recover the true distinct count within a

(1+\varepsilon)

factor. Experiments on image streams confirm that MaxSketch accurately estimates distinct counts and generalizes beyond the training regime. Our results bridge classical streaming algorithms and modern representation learning, showing how geometric structure can fundamentally reduce the complexity of distinct counting.

Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

National and Kapodistrian University of Athens, Greece · Archimedes, Athena Research Center, Greece · The University of Texas at Austin, USA

Locality-Sensitive Hashing Optimal Sample Complexity Counting Density Ratio Estimation Modern Data-Streaming Systems Sketches+3

Ask PDF

May 8, 2026cs.LG

Simple KNN-Based Outlier Detection Achieves Robust Clustering

Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the

\textit{robust

-Means}

problem (i.e.,

k

-Means with outliers), the goal is to remove

z

outliers and minimize the

k

-Means cost on the remaining points. Despite the close connection between robust

k

-Means and outlier detection, both theoretical and empirical understanding of the effectiveness of

\textit{classic outlier detection heuristics}

for robust

k

-Means remains limited. In this paper, we prove that under a practical assumption on the optimal cluster sizes, simply removing points with large

K

-Nearest-Neighbor distances achieves performance comparable to prior work in terms of approximation guarantees: it yields a constant-factor reduction from robust

k

-Means to standard

k

-Means, without introducing additional centers or discarding extra outliers, as is commonly required by existing approaches. Empirically, experiments on real-world datasets show that our method outperforms or matches several more sophisticated algorithms in terms of clustering cost and runtime. These results demonstrate that simple KNN-based heuristics can be surprisingly effective for robust clustering, highlighting new opportunities to bridge techniques from outlier detection and clustering.

Tianle Jiang, Yufa Zhou

Duke University

K-Means Clustering Outliers Approximate Nearest-Neighbor Search

Ask PDF

Apr 17, 2026cs.DS

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P,d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern and Zhang (2023) denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen (2020). For k-median and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints.

Nicole Funk, Annika Hennes, Johanna Hillebrand +1

Department of Informatics, University of Cologne, Germany · Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany · Department of Informatics, University of Bonn, Germany

K-Means Approximation Algorithms Clustering Algorithmic Fairness Maximum Mean Discrepancy Metric Spaces+1

Ask PDF