1 Search Results for "Zhong, Yu"

Document

DOI: 10.4230/LIPIcs.ESA.2021.13

k-Center Clustering with Outliers in the Sliding-Window Model

Authors: Mark de Berg, Morteza Monemizadeh, and Yu Zhong

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

The k-center problem for a point set P asks for a collection of k congruent balls (that is, balls of equal radius) that together cover all the points in P and whose radius is minimized. The k-center problem with outliers is defined similarly, except that z of the points in P do need not to be covered, for a given parameter z. We study the k-center problem with outliers in data streams in the sliding-window model. In this model we are given a possibly infinite stream P = ⟨ p₁,p₂,p₃,…⟩ of points and a time window of length W, and we want to maintain a small sketch of the set P(t) of points currently in the window such that using the sketch we can approximately solve the problem on P(t). We present the first algorithm for the k-center problem with outliers in the sliding-window model. The algorithm works for the case where the points come from a space of bounded doubling dimension and it maintains a set S(t) such that an optimal solution on S(t) gives a (1+ε)-approximate solution on P(t). The algorithm uses O((kz/ε^d)log σ) storage, where d is the doubling dimension of the underlying space and σ is the spread of the points in the stream. Algorithms providing a (1+ε)-approximation were not even known in the setting without outliers or in the insertion-only setting with outliers. We also present a lower bound showing that any algorithm that provides a (1+ε)-approximation must use Ω((kz/ε)log σ) storage.

Cite as

Mark de Berg, Morteza Monemizadeh, and Yu Zhong. k-Center Clustering with Outliers in the Sliding-Window Model. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ESA.2021.13,
  author =	{de Berg, Mark and Monemizadeh, Morteza and Zhong, Yu},
  title =	{{k-Center Clustering with Outliers in the Sliding-Window Model}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.13},
  URN =		{urn:nbn:de:0030-drops-145945},
  doi =		{10.4230/LIPIcs.ESA.2021.13},
  annote =	{Keywords: Streaming algorithms, k-center problem, sliding window, bounded doubling dimension}
}

Refine by Author
1 Monemizadeh, Morteza
1 Zhong, Yu
1 de Berg, Mark

Refine by Classification
1 Theory of computation → Design and analysis of algorithms

Refine by Keyword
1 Streaming algorithms
1 bounded doubling dimension
1 k-center problem
1 sliding window

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Zhong, Yu"

k-Center Clustering with Outliers in the Sliding-Window Model

Abstract

Cite as

Thanks for your feedback!

Could not send message