Better streaming algorithms for clustering problems

DOI10.1145/780542.780548MaRDI QIDQ3581265zbMATH OpenOpenAlexFDO

Authors Liadan O'Callaghan, Rina Panigrahy, Moses Charikar

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/780542.780548

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• An improved data stream algorithm for clustering
• Algorithms for \(k\)-median clustering over distributed streams
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• Metric \(k\)-median clustering in insertion-only streams

Cited in

(39)

• Data compression by volume prototypes for streaming data
• Correlation clustering in data streams
• Near-optimal clustering in the \(k\)-machine model
• A similarity function for feature pattern clustering and high dimensional text document classification
• Metric \(k\)-median clustering in insertion-only streams
• Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
• On the competitive ratio for online facility location
• Incremental algorithms for facility location and \(k\)-median
• Tolerant property testing and distance approximation
• Algorithms for \(k\)-median clustering over distributed streams
• Accurate low-space approximation of metric k-median for insertion-only streams
• Sublinear‐time approximation algorithms for clustering via random sampling
• Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity
• Pass-efficient algorithms for learning mixtures of uniform distributions
• The space complexity of pass-efficient algorithms for clustering
• Sublinear-time Algorithms
• Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
• Simulating random walks on graphs in the streaming model
• Robust communication-optimal distributed clustering algorithms
• Clustering on sliding windows in polylogarithmic space
• Streaming k-means on well-clusterable data
• Data reduction for weighted and outlier-resistant clustering
• scientific article; zbMATH DE number 7651177 (Why is no real title available?)
• Small Space Stream Summary for Matroid Center
• Improved Algorithms for Time Decay Streams
• scientific article; zbMATH DE number 7650129 (Why is no real title available?)
• Fully dynamic \(k\)-center clustering with outliers
• Fast modified global \(k\)-means algorithm for incremental cluster construction
• Single-pass streaming algorithms for correlation clustering
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Online facility location with weights and congestion
• Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
• Unexpected effects of online no-substitution k-means clustering
• No-substitution k-means clustering with adversarial order
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• An update algorithm for restricted random walk clustering for dynamic data sets
• Deterministic k-median clustering in near-optimal time
• A randomized algorithm for online unit clustering
• Small space representations for metric min-sum k-clustering and their applications

This page was built for publication: Better streaming algorithms for clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581265)