Data stream clustering: Difference between revisions

Revision as of 17:20, 15 January 2010

Revision as of 17:22, 15 January 2010

Line 15:

These algorithms have many similarities with [[online algorithms]] but they are not identical. 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.

Since data stream algorithms have limited memory available, the first goal is to show that clustering can take place in small space (not caring about the number of passes). Small-Space <ref>S. Guha, A. Meyerson, N. Mishra, R. Motwani, L. O’Callaghan, "Clustering Data Streams: Theory and Practice", IEEE Transactions on Knowledge and Data Engineering, Vol. 15, 2003<\ref> is a [[divide-and-conquer algorithm]] that divides the data into pieces, clusters each one of them (using k-means) and then clusters the centers obtained (each center is weighted by the number of points assigned to it)

Some of the most well-known algorithms used for data stream clustering include: