Streaming method improves selection of diverse points ignoring outliers
Streaming algorithms for robust max-min diversification
Machine Learning
Summary
Choosing a set of points that are as far apart as possible is useful in many fields but can be easily spoiled by a few unusual or noisy points. The authors improve on a previous streaming algorithm that tried to solve this by ignoring such outliers but had memory and accuracy issues. Their new approach uses less memory, always finds a full set of points, and more reliably excludes bad outliers. This method works efficiently for long data streams and adjusts to certain data space properties, making it practical for large, streaming datasets.
What this means in practice
- •For data engineers: Efficiently select well-spaced representative points from large or streaming data while ignoring noisy outliers, using fixed memory independent of dataset size.
- •For geospatial analysts: Produce diverse location samples from streaming spatial data without being skewed by abnormal or erroneous points.
Authors
Andrea Pietracaprina, Geppino Pucci, Stefano Zanon
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$.