Data stream clustering: Difference between revisions

Revision as of 22:16, 5 February 2010

Revision as of 18:32, 8 February 2010

Line 21:

'''''Theorem''': STREAM can solve the k-Median problem on a data stream with time O(n^1+e) and space θ(n^ε) up to a factor 2^O(1/e), where n the number of points and e<1/2''.

TheTo understand STREAM, the first goal is to show that clustering can take place in small space (not caring about the number of passes). Small-Space is a [[divide-and-conquer algorithm]] that divides the data, ''S'', into ''l'' pieces, clusters each one of them (using k-means) and then clusters the centers obtained.

[[File:Small-Space.jpg | thumb | 440x140px | right | Small-Space Algorithm representation]]

Line 42:

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.

The actual STREAM algorithm works as follows:

<ol>

<li> Input the first ''O(M/k)'' points, where ''M'' denotes bounded memory and ''k'' number of centers. Using the randomized algorithm presented in <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> cluster this to ''2k'' intermediate median points.

<li> Use a local search algorithm to cluster'' O(M)'' intermediate medians of level ''i'' to ''2k'' medians of level ''i+1''.

<li> Use the primal dual algorithm <ref> K. Jain and V. Vazirani. [http://portal.acm.org/citation.cfm?id=796509 Primal-dual approximation algorithms for metric facility ___location and k-median problems.] Proc. FOCS, 1999<\ref> to cluster the ''O(M)'' medians to k medians.

</ol>

=== Other Algorithms ===