Abstract
We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k--Median problem which produces a constant factor approximation in one pass using storage space O(k poly log n). This is a significant improvement of the previous best algorithm which yielded a 2O(1/ε) approximation using O(nε) space. Next we give a streaming algorithm for the k--Median problem with an arbitrary distance function. We also study algorithms for clustering problems with outliers in the streaming model. Here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.
Keywords
Streaming algorithmCluster analysisApproximation algorithmConstant (computer programming)OutlierComputer scienceAlgorithmSet (abstract data type)Space (punctuation)Fraction (chemistry)Function (biology)Data stream clusteringMathematicsCURE data clustering algorithmCorrelation clusteringArtificial intelligenceUpper and lower boundsMathematical analysis
Affiliated Institutions
Related Publications
On coresets for k-means and k-median clustering
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that gi...
Approximation schemes for clustering problems
Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation ...
A local search approximation algorithm for k-means clustering
In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to...
Clustering data streams: theory and practice
The data stream model has recently attracted attention for its applicability to numerous types of data, including telephone records, Web documents, and clickstreams. For analysi...
Model-Based Clustering, Discriminant Analysis, and Density Estimation
Cluster analysis is the automated search for groups of related observations in a dataset. Most clustering done in practice is based largely on heuristic but intuitively reasonab...
Publication Info
- Year
- 2003
- Type
- article
- Pages
- 30-39
- Citations
- 236
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
236
OpenAlex
Cite This
Moses Charikar,
Liadan O'Callaghan,
Rina Panigrahy
(2003).
Better streaming algorithms for clustering problems.
, 30-39.
https://doi.org/10.1145/780542.780548
Identifiers
- DOI
- 10.1145/780542.780548