Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
verfasst von : Richard Matthew McCutchen, Samir Khuller
Erschienen in: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Clustering is a common problem in the analysis of large data sets.
Streaming
algorithms, which make a single pass over the data set using small working memory and produce a clustering comparable in cost to the optimal offline solution, are especially useful. We develop the first streaming algorithms achieving a constant-factor approximation to the cluster radius for two variations of the
k
-center clustering problem. We give a streaming (4 +
ε
)-approximation algorithm using
O
(
ε
− 1
kz
) memory for the problem with
outliers
, in which the clustering is allowed to drop up to
z
of the input points; previous work used a random sampling approach which yields only a bicriteria approximation. We also give a streaming (6 +
ε
)-approximation algorithm using
O
(
ε
− 1
ln (
ε
− 1
)
k
+
k
2
) memory for a variation motivated by anonymity considerations in which each cluster must contain at least a certain number of input points.