Content deleted Content added
Line 15:
<!-- Unlike online algorithms, algorithms for data stream clustering have only a bounded amount of memory available and they may be able to take action after a group of points arrives while online algorithms are required to take action after each point arrives. -->
==== STREAM ====
STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan <ref>S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.1927 Clustering Data Streams]. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000</ref> which achieves a constant factor approximation for the k-Median problem in a single pass and using small space.
Line 43:
Where, at step (2) we use a bi-criteria ''(a,b)''-[[approximation algorithm | approximation algorithm]] which outputs at most ''ak'' medians with cost at most ''b'' <math>\forall</math> optimum and at step (3) we run a c-approximation algorithm. The approximation factor of Small-Space() algorithm is ''2c(1+2b)+2b''. We can also generalize it so that it recursively calls itself <math>i</math> times on a successively smaller set of weighted centers.
==== Other Algorithms ====
Other well-known algorithms used for data stream clustering are:
| |||