Better streaming algorithms for clustering problems

DOI10.1145/780542.780548zbMath1192.68350OpenAlexW2091684877MaRDI QIDQ3581265

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)

Related Items (23)

A randomized algorithm for online unit clustering ⋮ Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ A similarity function for feature pattern clustering and high dimensional text document classification ⋮ Fast modified global \(k\)-means algorithm for incremental cluster construction ⋮ Fully dynamic \(k\)-center clustering with outliers ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams ⋮ Data compression by volume prototypes for streaming data ⋮ Small Space Stream Summary for Matroid Center ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ Improved Algorithms for Time Decay Streams ⋮ On the competitive ratio for online facility location ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Sublinear-time Algorithms ⋮ Unnamed Item ⋮ Incremental algorithms for facility location and \(k\)-median ⋮ Tolerant property testing and distance approximation ⋮ Correlation clustering in data streams ⋮ An update algorithm for restricted random walk clustering for dynamic data sets ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Algorithms for k-median Clustering over Distributed Streams ⋮ Sublinear‐time approximation algorithms for clustering via random sampling

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