Data stream clustering: Difference between revisions

Revision as of 19:38, 29 January 2010

Revision as of 19:40, 29 January 2010

Line 21:

The approximation factor of this algorithm is <math>2c(1+2b)+2b</math> and if we generalize it so that it recursively calls itself, <math>i</math> times on a successively smaller set of weighted centers then it gives a constant factor approximation to the k-median problem, which, as expected, worsens with each successive reclustering.

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 approcimationapproximation algorithm for the k-Median problem in a single pass.

Some others well-known algorithms used for data stream clustering include:

Line 38:

http://www.springerlink.com/content/uc06wwfpc8wl04wf/fulltext.pdf

Requirements for Clustering Data Streams, Daniel Barbara