Data stream clustering: Difference between revisions

Revision as of 19:41, 11 February 2010

Revision as of 21:38, 11 February 2010

Line 22:

STREAM is an algorithm for clustering data streams described by Guha, Mishra, Motwani and O'Callaghan <ref name=cds > 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.

'''''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''.

To understand STREAM, the first goalstep 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''<math>\ell</math> 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 32:

<ol>

<li> Divide ''S'' into ''l'' disjoint pieces ''χX''₁,...,χ''X''_{l<math>_{\ell}</math>}''.</li>

<li> For each ''i'', find ''O(k)'' centers in ''χX_i'', using ''k''-means. Assign

each point in ''χX_i'' to its closest center.</li>

<li> Let ''χX''' be the ''O(lk<math>\ell</math>k)'' centers obtained in (2),

where each center ''c'' is weighted by the number

of points assigned to it.</li>

<li> Cluster ''χX''' to find ''k'' centers.</li>

</ol>

Line 44:

<br />

Where, atif stepin Step (2) we userun a bi-criteriabicriteria ''(a,b)''-[[approximation algorithm | approximation algorithm]] which outputs at most ''ak'' medians with cost at most ''b'' <math>\forall</math>times the optimum k-Median solution and atin stepStep (3)4 we run a ''c''-approximation algorithm. Thethen the approximation factor of Small-Space() algorithm is ''2c(1+2b)+2b''. We can also generalize itSmall-Space so that it recursively calls itself <math>''i</math>'' times on a successively smaller set of weighted centers and achieves a constant factor approximation to the ''k''-median problem.

The problem with the Small-Space is that the number of subsets <math>\ell</math> that we partition ''S'' into is limited, since it has to store in memory the intermediate medians in ''X'''. So, if ''M'' is the size of memory, we need to partition ''S'' into <math>\ell</math> subsets such that each subset fits in memory, (n/<math>\ell</math>) and so that the weighted <math>\ell</math>''k'' centers also fit in memory, <math>\ell</math>''k<M''. But such an <math>\ell</math> may not always exist.

The actual STREAM algorithm works as follows:

The STREAM algorithm solves the problem of storing intermediate medians and achieves better running time and space requirements. The 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 name=cds /> cluster this to ''2k'' intermediate median points.