Fetching the paper…
Reading the bibliography…
We consider the $k$-means clustering problem in the dynamic streaming setting, where points from a discrete Euclidean space $\{1, 2, \ldots, \Delta\}^d$ can be dynamically inserted to or deleted from the dataset.
Decomposable searching problems i. static-to-dynamic transformation
Jon Louis Bentley and James B Saxe · 1980
Earlier work this paper cites.
Least squares quantization in pcm
Stuart Lloyd · 1982
Earlier work this paper cites.
Randomness-efficient oblivious sampling
Mihir Bellare and John Rompel · 1994
Earlier work this paper cites.
Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median
Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha · 1998
Earlier work this paper cites.
Clustering data streams
Sudipto Guha, Nina Mishra, R. Motwani, and L. O’Callaghan · 2000
Earlier work this paper cites.
Counting distinct elements in a data stream
Ziv Bar-Yossef, TS Jayram, Ravi Kumar, D Sivakumar, and Luca Trevisan · 2002
Earlier work this paper cites.
A local search approximation algorithm for k-means clustering
Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu · 2002
Earlier work this paper cites.
Maintaining variance and k-medians over data stream windows
Brain Babcock, Mayur Datar, Rajeev Motwani, and Liadan O’Callaghan · 2003
Earlier work this paper cites.
Better streaming algorithms for clustering problems
Moses Charikar, Liadan O’Callaghan, and Rina Panigrahy · 2003
Earlier work this paper cites.
Approximating extent measures of points
Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan · 2004
Earlier work this paper cites.
On coresets for k-means and k-median clustering
Sariel Har-Peled and Soham Mazumdar · 2004
Earlier work this paper cites.
Algorithms for dynamic geometric problems over data streams
Piotr Indyk · 2004
Earlier work this paper cites.
On graph problems in a semi-streaming model
Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang · 2005
Earlier work this paper cites.
Coresets in dynamic geometric data streams
Gereon Frahling and Christian Sohler · 2005
Earlier work this paper cites.
Sampling in dynamic data streams and applications
Gereon Frahling, Piotr Indyk, and Christian Sohler · 2005
Earlier work this paper cites.
Counting distinct items over update streams
Sumit Ganguly · 2005
Earlier work this paper cites.
Smaller coresets for k-median and k-means clustering
Sariel Har-Peled and Akash Kushal · 2005
Cited alongside, same era.
Data streams: Algorithms and applications
Shanmugavelayutham Muthukrishnan · 2005
Cited alongside, same era.
A ptas for k-means clustering based on weak coresets
Dan Feldman, Morteza Monemizadeh, and Christian Sohler · 2007
Cited alongside, same era.
Streaming algorithm for graph spanners-single pass and constant processing time per edge
Surender Baswana · 2008
Cited alongside, same era.
Np-hardness of euclidean sum-of-squares clustering
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat · 2009
Cited alongside, same era.
On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications
Ke Chen · 2009
Cited alongside, same era.
Dynamic graphs in the sliding-window model
Michael S Crouch, Andrew McGregor, and Daniel Stubbs · 2013
Later among the works it cites.
New approximability results for the robust k-median problem
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann · 2014
Later among the works it cites.
Graph stream algorithms: a survey
Andrew McGregor · 2014
Later among the works it cites.
Fully dynamic maximal matching in o( log n \log n ) update time
Surender Baswana, Manoj Gupta, and Sandeep Sen · 2015
Later among the works it cites.
Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos Tsourakakis · 2015
Later among the works it cites.
Dimensionality reduction for k-means clustering and low rank approximation
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The planar k-means problem is np-hard
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2009
Cited alongside, same era.
Data clustering: 50 years beyond k-means
Anil K Jain · 2010
Cited alongside, same era.
Linear-time approximation schemes for clustering problems in any dimensions
Amit Kumar, Yogish Sabharwal, and Sandeep Sen · 2010
Cited alongside, same era.
A unified framework for approximating and clustering data
Dan Feldman and Michael Langberg · 2011
Cited alongside, same era.
K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
Piotr Indyk and Eric Price · 2011
Cited alongside, same era.
Spectral sparsification in the semi-streaming setting
J. Kelner and A. Levin · 2011
Cited alongside, same era.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu · 2015
Later among the works it cites.
On fully dynamic graph sparsifiers
Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng · 2016
Later among the works it cites.
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
Arturs Backurs, Piotr Indyk, Eric Price, Ilya Razenshteyn, and David P Woodruff · 2016
Later among the works it cites.
Faster fully dynamic matchings with small approximation ratios
Aaron Bernstein and Cliff Stein · 2016
Later among the works it cites.
Optimal principal component analysis in distributed and streaming models
Christos Boutsidis, David P Woodruff, and Peilin Zhong · 2016
Later among the works it cites.
New frameworks for offline and streaming coreset constructions
Vladimir Braverman, Dan Feldman, and Harry Lang · 2016
Later among the works it cites.
Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics
Vincent Cohen-Addad, Philip N Klein, and Claire Mathieu · 2016
Later among the works it cites.
Local search yields a ptas for k-means in doubling metrics
Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour · 2016
Later among the works it cites.
Clustering high dimensional dynamic data streams
Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F Yang · 2017
Later among the works it cites.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, CN Musco, CP Musco, and Aaron Sidford · 2017
Later among the works it cites.
Strong coresets for k-median and subspace approximation, goodbye dimension
Christian Sohler and David P. Woodruff · 2018
Closest in time.