Better streaming algorithms for clustering problems

By Moses Charikar, Liadan O'Callaghan, Rina Panigrahy. Symposium on the Theory of Computing, 2003

313 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/1935d933d0e898794e17b92f9201586ec562fcc0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Organizational Behavior and Human Resource Management

Citations in the corpus

Density-Based Clustering over an Evolving Data Stream with Noise (2006, methodology): “Previous methods, one-pass [4, 10, 11] or evolving [1, 2, 5, 18], do not consider that the clusters in data streams could be of arbitrary shape.”
k-means++: the advantages of careful seeding (2007, unknown): “[6] in the context of k-median clustering.”
Maintaining variance and k-medians over data stream windows (2003, background): “[6] do in the stream model without sliding windows), rather than polynomial space, is an open problem.”
Data streams: algorithms and applications (2005, methodology): “In a recent result [101] on an improved algorithm for the k-median problem on data streams, in the first phase, aO(k polylog(n)) facility solution is obtain from which the algorithm culls t hek facilities which is provably1+ ǫ accurate.”
Social big data: Recent achievements and new challenges (2015, methodology): “A new generation of online [132, 133] and streaming [134, 135] algorithms is currently being developed in order to manage social big data challenges, and these algorithms require high scalability in both memory consumption [136] and time computation.”
Issues in data stream management (2003, background): “Recent results in (approximate) algorithms for on-line stream mining include computing stream signatures and representative trends [21], decision trees [44], forecasting [71], k-medians clustering [16, 42], nearest neighbour queries [46], and regression analysis [18].”
On coresets for k-means and k-median clustering (2004, background): “[27] improve the algorithm by reducing the space requirement to O(k · polylog(n)).”
Mining data streams: a review (2005, methodology): “Charikar et al [ 11 ] have proposed another kmedian algorithm that overcomes the problem of increasing approximation factors in the Guha et al [27] algorithm with the increase in the number of levels used to result in the final solution of the divide and conquer algorithm.”