An improved data stream algorithm for clustering
type: Item
instance of: scholarly article
title: An improved data stream algorithm for clustering
zbMATH Open document ID: 1335.65031
author: Sang-Sub Kim
author: Hee-Kap Ahn
published in: Computational Geometry
publication date: 2016-01-15T00:00:00Z
review text: The paper deals with the problem of the \(k\)-center problem, i.e., given a set of points \(P\) in a metric space and an integer \(k\), we want to find \(k\) points \(c_1, c_2, \dots, c_k\) such that \(\max_{p \in P} \min_{1\leq i \leq k} |p c_i|\) is minimized, where \(|pq|\) denotes the distance between \(p\) and \(q\). The authors make some additional assumptions, namely they take the \(d\)-dimensional Euclidean metric space \(\mathbb R^d\). Moreover, they assume that the points arrive one by one in a stream and we are allowed to examine each point only once, and only a small amount of information can be stored in a device. The authors start with giving a single-pass data stream algorithm that for any \(d \geq 1\) uses the \(O(d / \varepsilon)\) space and returns two centers together with their radii that guarantee a \((1.8 + \varepsilon)\)-approximation for the Euclidean \(2\)-center problem. Each update in the algorithm takes \(O(d / \varepsilon)\) time. Later, they extend the algorithm to the Euclidean \(k\)-center problem. They design an approximation algorithm that for some constant \(k > 2\) and for any dimension \(d \geq 1\) uses \(O(2^k (k+3)! d / \varepsilon )\) space and returns \(k\) centers that guarantee a \((1.8 + \varepsilon)\)-approximation. Each update in the algorithm takes \(O(2^k (k+2)! d / \varepsilon)\) time.
reviewed by: Krzysztof Gdawiec
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 6531077
zbMATH Keywords: Euclidean \(k\)-clustering
zbMATH Keywords: Euclidean \(k\)-center problem
zbMATH Keywords: streaming algorithms
zbMATH Keywords: computational geometry
MaRDI profile type: Publication
full work available at URL: j.comgeo.2015.06.003
OpenAlex ID: W2215609590
cites work: Q5417724
cites work: Data streams. Models and algorithms.
cites work: COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k
cites work: Streaming and dynamic algorithms for minimum enclosing balls in high dimensions
cites work: Incremental Clustering and Dynamic Information Retrieval
cites work: Q4198056
cites work: Data mining. Concepts and techniques
cites work: Adaptive sampling for geometric problems over data streams
cites work: Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
cites work: On the Complexity of Some Common Geometric Location Problems
cites work: Streaming with minimum space: an algorithm for covering by two congruent balls
DOI: 10.1016/J.COMGEO.2015.06.003
description: scientific article; zbMATH DE number 6531077