Data stream clustering

In computer science, data stream clustering is defined as the clustering of data that arrive continuously such as telephone records, multimedia data, financial transactions etc. Data stream clustering is usually studied under the data stream model of computation and the objective is, given a sequence of points, to maintain a consistently good clustering of the sequence observed so far, using a small amount of memory and time.

History

The problem of data stream clustering has recently attracted much attention for its applicability to emerging applications that involve large amount of streaming data such as network flows, sensor data, and web click streams. One of the first results on data streams was due to Munro and Paterson ^[1] but the model was formalized much later by Henzinger, Raghavan, and Rajagopalan ^[2]. K-means is a widely used heuristic for clustering but also alternate algorithms for clustering have been developed such as k-Medoids, CURE and the popular BIRCH.

Algorithms

Many algorithms have been proposed for the data stream clustering problem. The performance of an algorithm that operates on data streams is measured by three basic factors:

The number of passes the algorithm must make over the stream.
The available memory.
The running time of the algorithm.

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^[3] 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 (where each center is weighted by the number of points assigned to it).

Small-Space Algorithm representation

The approximation factor of this algorithm is $2c(1+2b)+2b$ and if we generalize it so that it recursively calls itself, $i$ 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 ^[4] which achieves a constant factor approcimation algorithm for the k-Median problem in a single pass.

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

BIRCH
COBWEB

References

^ J.Munro and M. Paterson. Selection and Sorting with Limited Storage. Theoretical Computer Science, pages 315-323, 1980
^ M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on Data Streams. Digital Equipment Corporation, TR-1998-011, August 1998.
^ S. Guha, A. Meyerson, N. Mishra, R. Motwani. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering, Volume 15, Issue 3, 2003
^ S. Guha, N. Mishra, R. Motwani, L. O'Callaghan. Clustering Data Streams. Proceedings of the Annual Symposium on Foundations of Computer Science, 2000