An improved data stream algorithm for clustering
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.
- An improved data stream algorithm for clustering
- Computing k centers over streaming data for small k
- Computing \(k\)-center over streaming data for small \(k\)
- On the Complexity of Approximation Streaming Algorithms for the k-Center Problem
- An adaptive probabilistic algorithm for online \(k\)-center clustering
- Adaptive sampling for geometric problems over data streams
- Computing k centers over streaming data for small k
- Data mining. Concepts and techniques
- Data streams. Models and algorithms.
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 6297803 (Why is no real title available?)
- Incremental Clustering and Dynamic Information Retrieval
- On the Complexity of Some Common Geometric Location Problems
- Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
- Streaming and dynamic algorithms for minimum enclosing balls in high dimensions
- Streaming with minimum space: an algorithm for covering by two congruent balls
- An adaptive probabilistic algorithm for online \(k\)-center clustering
- Computing k centers over streaming data for small k
- scientific article; zbMATH DE number 5811661 (Why is no real title available?)
- Better streaming algorithms for clustering problems
- On the Complexity of Approximation Streaming Algorithms for the k-Center Problem
- scientific article; zbMATH DE number 6874937 (Why is no real title available?)
- Computing \(k\)-center over streaming data for small \(k\)
- An improved data stream algorithm for clustering
- Data stream clustering
- (1 + )-approximation for facility location in data streams
- Small Space Stream Summary for Matroid Center
- Covering convex polygons by two congruent disks
- Covering convex polygons by two congruent disks
- Tight lower bounds for approximate \& exact \(k\)-center in \(\mathbb{R}^d\)
- A streaming algorithm for 2-center with outliers in high dimensions
- Moderate dimension reduction for k-center clustering
- k-center with outliers in sliding windows
This page was built for publication: An improved data stream algorithm for clustering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q904105)
